Fast low-rank modifications of the thin singular value decomposition

By Matthew Brand. 2006

555 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/c92642c04eda20476fb6c41f1ceb6fa84e7a35d4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Signal Processing

Citations in the corpus

Π-ORFit: One-Pass Learning with Bregman Projection (2024, methodology): “Once +1 can be obtained by repeating rank-1 update of SVD n times by appending each row of Φ k +1 at a Algorithm 1 describes the rank-1 update procedure for row vector addition [25].”
From Frequency to Meaning: Vector Space Models of Semantics (2010, background): “However, there are efficient forms of SVD (Brand, 2006; Gorrell, 2006).”
Memory Limited, Streaming PCA (2013, background): “, [4, 3], [6],[12] and more recently [2, 9]) seek to have the best subspace estimate at every time (i.”
Frequency Selective Hybrid Precoding for Limited Feedback Millimeter Wave Systems (2015, background): “ues calculation in (54) can be calculated as a rank-1 update of the previous iteration eigenvalues, which reduces the overall complexity [69].”
Millimeter Wave MIMO With Lens Antenna Array: A New Path Division Multiplexing Paradigm (2015, background): “For a low-rank M U × Q U channel matrix of rank L , the complexity can be reduced to O ( M U Q U L ) by exploiting its low-rank property [46].”
Online identification and tracking of subspaces from highly incomplete information (2010, methodology): “Brand [11] has shown that this method can be used to compute an efficient incremental update of an SVD using optimized algorithms for computing rank one modifications of matrix factorizations [12].”
Similarity Scores Based on Background Samples (2009, methodology): “If SW is not full rank, a similar formula can be applied to update the pseudoinverse, based on rank-one updates [24] of the Cholesky factor or SVD of SA.”
Relational Representation Learning for Dynamic (Knowledge) Graphs: A Survey (2019, background): “Brand [21] propose an efﬁcient way to update the singular value decomposition of a matrix S when another lower rank matrix of the same size ∆ S is added to it.”
Nonlinear model order reduction based on local reduced‐order bases (2012, methodology): “u0 Q u0/1 T Ns (16) is a rank one update of Y, the singular value decomposition update procedure proposed in [23] can be applied in this case as is.”
Effective Unconstrained Face Recognition by Combining Multiple Descriptors and Learned Background Statistics (2011, unknown): “If SW is not full rank, a similar formula can be applied to update the pseudo-inverse, based on rank-one updates [55] of the Cholesky factor or SVD of SA.”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “Let S n − 1 and V n − 1 be the corresponding matrices for this thin SVD so that We then notice as in [52,53] that where w n = U Tn − 1 x n are the projection weights onto the span of this now tall matrix x n is the residual from the projection.”
An Online Spectral Learning Algorithm for Partially Observable Nonlinear Dynamical Systems (2011, methodology): “Our method leverages fast, low-rank modifications of the thin singular value decomposition (Brand 2006), and uses tricks such as random projections to scale to extremely large numbers of examples and features per example.”
Representation Learning for Dynamic Graphs: A Survey (2019, methodology): “Brand (2006) proposes an efficient way to update the singular value decomposition of a matrix S when another lower rank matrix of the same size ∆S is added to it. Consider the problem in Equation (12). If one knows the solution (Us,Ut,Σ) and ∆S is an update of the matrix, one can find a general form”