An important task when processing sensor data is to distinguish relevant from irrelevant data. This paper describes a method for an iterative singular value decomposition that maintains a model of the background via singular vectors spanning a subspace of the image space, thus providing a way to determine the amount of new information contained in an incoming frame. We update the singular vectors spanning the background space in a computationally efficient manner and provide the ability to perform block-wise updates, leading to a fast and robust adaptive SVD computation. The effects of those two properties and the success of the overall method to perform a state of the art background subtraction are shown in both qualitative and quantitative evaluations.
There already exist iterative methods to calculate an SVD, but for our purpose the approach from @cite_9 has two favorable aspects. The first one is the possibility to perform blockwise updates with @math , that is, with several frames. The second one is the ability to estimate the effect of appending @math on the singular values of @math . In order to compute the SVD of @math , @math is first calculated and a QR decomposition with column pivoting of @math is determined. The @math matrix contains the information in the added data @math that is not already described by the singular vectors in @math . Then, the matrix @math can be truncated by a significance level @math such that the singular values less than @math are set to zero in the SVD calculation of [ . ] Therefore, one can determine only from the (cheap) calculation of a QR decomposition, whether the new data contains significant new information and the threshold level @math can control how big the gain has to be for a data vector to be added to the current SVD decomposition in an iterative step.
@cite_9
2892093392
Abstract We consider the problem of updating the SVD when augmenting a “tall thin” matrix, i.e., a rectangular matrix A ∈ R m × n with m ≫ n . Supposing that an SVD of A is already known, and given a matrix B ∈ R m × n ′ , we derive an efficient method to compute and efficiently store the SVD of the augmented matrix [ A B ] ∈ R m × ( n + n ′ ) . This is an important tool for two types of applications: in the context of principal component analysis, the dominant left singular vectors provided by this decomposition form an orthonormal basis for the best linear subspace of a given dimension, while from the right singular vectors one can extract an orthonormal basis of the kernel of the matrix. We also describe two concrete applications of these concepts which motivated the development of our method and to which it is very well adapted.