Spectral norm of products of random and deterministic matrices

By Roman Vershynin. 2008

83 citations recorded by the source corpus.

We study the spectral norm of matrices W that can be factored as W = BA, where A is a random matrix with independent mean zero entries and B is a fixed matrix. Under the (4 + ε)th moment assumption on the entries of A, we show that the spectral norm of such an m × n matrix W is bounded by $${\sqrt{m} + \sqrt{n}}$$, which is sharp. In other words, in regard to the spectral norm, products of random and deterministic matrices behave similarly to random matrices with independent entries. This result along with the previous work of Rudelson and the author implies that the smallest singular value of a random m × n matrix with i.i.d. mean zero entries and bounded (4 + ε)th moment is bounded below by $${\sqrt{m} - \sqrt{n-1}}$$ with high probability.

Subfields: Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/800d2f87dc23dab91ca3a8145e13ef7ef3efc62b

How researchers see this paper

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

In Mathematical Physics

In Statistics and Probability

Citations in the corpus

Invertibility of Sparse non-Hermitian matrices (2015, background): “Finally a matching upper bound was proved for sub-Gaussian entries in [22], and improved under finite fourth moment assumption in [31].”
Random matrix theory in statistics: A review (2014, background): “One may refer to Vershynin (2011) or Vershynin (2012) for detailed discussions on such applications.”
Non-asymptotic theory of random matrices: extreme singular values (2010, background): “Non-asymptotic estimate (3.3) was extended to matrices whose entries have ﬁnite (4 + ε )-th moment in [93].”
Simple and deterministic matrix sketching (2012, background): “Due to [25], the spectral norms of SDU and N are expected to be the same up to some constant.”
Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization (2009, background): “Moving from k A k 2 , 2 = sup x , y ∈ S m − 1 x ∗ A y to our product of nets loses at most a constant factor in the estimate: k A k 2 , 2 ≤ 4 sup x , y ∈ N x ∗ A y (see e.g., [29] Proposition 2.6).”
Lower bounds for the smallest singular value of structured random matrices (2016, background): “, centered entries Yij ∈ Rhaving ﬁnite fourth moment. Then (5.6) EkY k ≪ max i∈[n] Xm j=1 EY2 ij ! 1/2 + max j∈[m] Xn i=1 EY2 ij ! 1/2 + Xn i=1 Xm j=1 EY4 ij ! 1/4 . 46 N. COOK Theorem 5.8 (Vershynin [42]). Let η ∈ (0,1) and n,m,N suﬃciently large natural numbers. Let D ∈ Mm,N(R) be a deterministic ”
Hanson-Wright inequality and sub-gaussian concentration (2013, background): “trix Gwith independent sub-gaussian entries satisﬁes kBGk . kBkHS + √ nkBk with high probability. For random matrices with heavy-tailed rather than subgaussian components, this problem was studied in [17]. Theorem 3.2 (Norms of random matrices). Let Bbe a ﬁxed m× N matrix, and let Gbe an N× nrandom ”
The smallest singular value of inhomogeneous square random matrices (2019, background): “The behavior of the smallest singular values of random matrices have been extensively studied [2, 4, 5, 11, 15, 16, 17, 20, 22, 24, 25, 26, 33, 34, 35, 36, 37, 38, 39, 40, 41, 43].”
Sums of random Hermitian matrices and an inequality by Rudelson (2010, background): “We also prove a concentration inequality for sums of random matrices of rank one with explicit constants.”
Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics (2016, background): “35 in Vershynin (2012) yields P(σmin(W ) < 1/2) ≤ exp(−cp1).”