Perturbation bounds in connection with singular value decomposition

By Per-Åke Wedin. 1972

Subfields: Statistical Learning Theory, Numerical Methods & Scientific Computing

How researchers see this paper

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

In Statistical Learning Theory

In Numerical Methods & Scientific Computing

Citations in the corpus

Guaranteed Matrix Completion via Non-Convex Factorization (2014, methodology): “Our regularizers are smooth functions with simple gradients, thus the algorithms for our formulation have similar per-iteration computation cost as the algorithms for the formulation without regularizers.”
Tensor decompositions for learning latent variable models (2012, methodology): “The following theorem is similar to Wedin’s perturbation theorem for singular vectors of matrices (Wedin, 1972) in that it bounds the error of the (approximate) decomposition returned by Algorithm 1 on input T̂ in terms of the size of the perturbation, provided that the perturbation is small enough.”
ECA: High-Dimensional Elliptical Component Analysis in Non-Gaussian Distributions (2013, background): “The approximation error of u1(K̂) to u1(K) is related to the convergence of K̂ to K under the spectral norm via the Davis–Kahan inequality (Davis and Kahan 1970; Wedin 1972).”
A Practical Algorithm for Topic Modeling with Provable Guarantees (2012, methodology): “√ This follows from Wedin’s Theorem [Wedin, 1972] and the fact that Now we are ready to prove Lemma A.1.”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, background): “Here, m atrix Bernstein inequality [10, 11] and Wedin’s theorem [13] implies the fol lowing standard sample complexity bound for the Streaming PCA problem:”
Sparse Principal Component Analysis and Iterative Thresholding (2011, background): “Otherwise, A proof is given in the appendix, the key ingredient of which is Wedin’s sin θ theorem for singular subspaces [35].”
Structured Latent Factor Analysis for Large-scale Data: Identifiability, Estimability, and Their Implications (2017, methodology): “Moreover, the sine measure is a canonical way to quantify the distance between two linear spaces that has been used in, for example, the well-known sine theorems for matrix perturbation(Davis, 1963; Wedin, 1972).”
Sparse PCA: Optimal rates and adaptive estimation (2012, methodology): “Hence we obtain the SVD of (64) as ˜ Σ = ˜ V ˜ Λ ˜ V ′ + I p .”
Sequential Transfer in Multi-armed Bandit with Finite Set of Models (2013, unknown): “In the case of‖U − Û‖ we rely on the perturbation bound of Wedin (1972).”
Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution (2017, unknown): “Proof This follows from Wedin’s sin theorem [121] and [76, Lemma 5.”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, background): “Several generalizations and extensions have been made in different settings after the seminal work of Wedin (1972).”
Item Response Theory—A Statistical Framework for Educational and Psychological Measurement (2021, unknown): “By making use of (3.4) and by proving extensions of the Davis-Kahan-Wedin sine theorem (Davis and Kahan, 1970; Wedin, 1972) for the perturbation of eigenvectors, it can be shown under suitable conditions that (3.5) Under the typical setting where N is much larger than J , the rates in (3.4) and…”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, methodology): “It follows from well-known estimates in extreme value theory [126] that”
Depth Creates No Bad Local Minima (2017, unknown): “Σ2 = diag(¯σk+1,···,σ¯n), U, V , U¯ and V¯ are orthogonal matrices. Lemma 3.1. Continuity of Singular Value The singular value σi of a matrix is a continuous map of entries of the matrix. Lemma 3.2. (Wedin, 1972) Continuity of Singular Space 3 If ρ := min ˆ min 1≤i≤k,1≤j≤n−k |σi −σ¯k+j|, min 1≤i≤k σ”
High-Dimensional Gaussian Process Bandits (2013, background): “Because the DS will find a matrix X̂ close to X , due to a result by Wedin [24] we know that the learned subspace will be close to the true one.”