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
2119759375 1997863462 2020828929 2087716616
This paper concerns accurate computation of the singular value decomposition (SVD) of an (m n ) matrix (A ). As is well known, cross-product matrix based SVD algorithms compute large singular values accurately but generally deliver poor small singular values. A new novel cross-product matrix based SVD method is proposed: (a) Use a backward stable algorithm to compute the eigenpairs of (A^ T A ) and take the square roots of the large eigenvalues of it as the large singular values of (A ) ; (b) form the Rayleigh quotient of (A^ T A ) with respect to the matrix consisting of the computed eigenvectors associated with the computed small eigenvalues of (A^ T A ) ; (c) compute the eigenvalues of the Rayleigh quotient and take the square roots of them as the small singular values of (A ). A detailed quantitative error analysis is conducted on the method. It is proved that if small singular values are well separated from the large ones then the method can compute the small ones accurately up to the order of the unit roundoff ( ). An algorithm is developed that is not only cheaper than the standard Golub–Reinsch and Chan SVD algorithms but also can update or downdate a new SVD by adding or deleting a row and compute certain refined Ritz vectors for large matrix eigenproblems at very low cost. Several variants of the algorithm are proposed that compute some or all parts of the SVD. Typical numerical examples confirm the high accuracy of our algorithm. Singular Value Decomposition (SVD) is computationally costly and therefore a naive implementation does not scale to the needs of scenarios where data evolves continuously. While there are various on-line analysis and incremental decomposition techniques, these may not accurately represent the data or may be slow for the needs of many applications. To address these challenges, in this paper, we propose a Low-rank, Windowed, Incremental SVD (LWI-SVD) algorithm, which (a) leverages efficient and accurate low-rank approximations to speed up incremental SVD updates and (b) uses a window-based approach to aggregate multiple incoming updates (insertions or deletions of rows and columns) and, thus, reduces on- line processing costs. We also present an LWI-SVD with restarts (LWI2-SVD) algorithm which leverages a novel highly efficient partial reconstruction based change detection scheme to support timely refreshing of the decomposition with significant changes in the data and prevent accumulation of errors over time. Experiment results, including comparisons to other state of the art techniques on different data sets and under different parameter settings, confirm that LWI-SVD and LWI2-SVD are both efficient and accurate in maintaining decompositions. This paper is the result of concerted efforts to break the barrier between numerical accuracy and run-time efficiency in computing the fundamental decomposition of numerical linear algebra—the singular value decomposition (SVD) of general dense matrices. It is an unfortunate fact that the numerically most accurate one-sided Jacobi SVD algorithm is several times slower than generally less accurate bidiagonalization-based methods such as the QR or the divide-and-conquer algorithm. Our quest for a highly accurate and efficient SVD algorithm has led us to a new, superior variant of the Jacobi algorithm. The new algorithm has inherited all good high accuracy properties of the Jacobi algorithm, and it can outperform the QR algorithm. Abstract Most methods for calculating the SVD (singular value decomposition) require to first bidiagonalize the matrix. The blocked reduction of a general, dense matrix to bidiagonal form, as implemented in ScaLAPACK, does about one half of the operations with BLAS3. By subdividing the reduction into two stages dense → banded and banded → bidiagonal with cubic and quadratic arithmetic costs, respectively, we are able to carry out a much higher portion of the calculations in matrix–matrix multiplications. Thus, higher performance can be expected. This paper presents and compares three parallel techniques for reducing a full matrix to banded form. (The second reduction stage is described in another paper [B. Lang, Parallel Comput. 22 (1996) 1–18]). Numerical experiments on the Intel Paragon and IBM SP 1 distributed memory parallel computers demonstrate that the two-stage reduction approach can be significantly superior if only the singular values are required.