Spectral norm of products of random and deterministic matrices

DOI10.1007/S00440-010-0281-ZMaRDI QIDQ718893zbMATH OpenOpenAlexFDO

Authors Roman Vershynin

Publication date 27 September 2011

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.2432

zbMATH Keywords

singular valuessample covariance matricesnon-asymptotic random matrix bounds

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15)

Abstract: We study the spectral norm of matrices M that can be factored as M=BA, where A is a random matrix with independent mean zero entries, and B is a fixed matrix. Under the (4+epsilon)-th moment assumption on the entries of A, we show that the spectral norm of such an m by n matrix M 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 M. Rudelson and the author implies that the smallest singular value of a random m times n matrix with i.i.d. mean zero entries and bounded (4+epsilon)-th moment is bounded below by sqrt{m} - sqrt{n-1} with high probability.

Recommendations

• Spectral norm of random matrices
• Spectral radii of products of random rectangular matrices
• The norm of the product of a large matrix and a random vector
• The spectral norm of random lifts of matrices
• On the spectral norm of Gaussian random matrices
• On the singular spectrum of powers and products of random matrices
• On asymptotics for the spectrum of the product of two random rectangular matrices
• On the spectral norm of a random Toeplitz matrix
• Products of random matrices: dimension and growth in norm
• The spectral radius of a product of nonnegative matrices

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1302647 (Why is no real title available?)
• A new look at independence
• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• A universality result for the smallest eigenvalues of certain sample covariance matrices
• Advanced Lectures on Machine Learning
• Concentration of mass on convex bodies
• Condition numbers of random matrices
• Eigenvalues and Condition Numbers of Random Matrices
• Exact separation of eigenvalues of large dimensional sample covariance matrices
• Invertibility of random matrices: norm of the inverse
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Lower estimates for the singular values of random matrices
• No eigenvalues outside the support of the limiting spectral distribution of large-dimensional sample covariance matrices
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• On uncomplemented subspaces of \(L_p\), \(1<p<2\)
• Polynomial bounds for large Bernoulli sections of _1N
• Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles
• RANDOM POINTS IN ISOTROPIC UNCONDITIONAL CONVEX BODIES
• Random matrices: The distribution of the smallest singular values
• Random vectors in the isotropic position
• Random walks and anO*(n5) volume algorithm for convex bodies
• Sampling convex bodies: a random matrix approach
• Smallest singular value of a random rectangular matrix
• Smallest singular value of random matrices and geometry of random polytopes
• Some estimates of norms of random matrices
• Sparse random matrices; Spectral edge and statistics of rooted trees
• The Expected Norm of Random Matrices
• The Littlewood-Offord problem and invertibility of random matrices
• The concentration of measure phenomenon
• The eigenvalues of random symmetric matrices
• The least singular value of a random square matrix is O\((n ^{- 1/2})\)

Cited in

(51)

• Norms of structured random matrices
• Matrix concentration for products
• LASSO risk and phase transition under dependence
• A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions
• Probably certifiably correct k-means clustering
• scientific article; zbMATH DE number 7306893 (Why is no real title available?)
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• Row products of random matrices
• Provable Phase Retrieval with Mirror Descent
• scientific article; zbMATH DE number 130628 (Why is no real title available?)
• Asymptotic geometric analysis: achievements and perspective
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• The discrepancy in min-max statistics between two random matrices with finite third moments
• Random matrix theory in statistics: a review
• Eigenvectors of random matrices: A survey
• Non-asymptotic bounds for the \(\ell_{\infty}\) estimator in linear regression with uniform noise
• Frequent directions: simple and deterministic matrix sketching
• On approximating matrix norms in data streams
• On the expectation of the norm of random matrices with non-identically distributed entries
• Tail Bounds on the Spectral Norm of Sub-Exponential Random Matrices
• Invertibility of sparse non-Hermitian matrices
• Lower bounds for the smallest singular value of structured random matrices
• Determining the upper bound of the spectral norm of a random matrix and its application to diagnosis of the Kalman filter
• Trace regression model with simultaneously low rank and row(column) sparse parameter
• The smallest singular value of inhomogeneous square random matrices
• Tensor sparsification via a bound on the spectral norm of random tensors: Algorithm 1.
• ROP: matrix recovery via rank-one projections
• Universality and sharp matrix concentration inequalities
• Spectral Distribution of Product of Pseudorandom Matrices Formed From Binary Block Codes
• The benefit of group sparsity in group inference with de-biased scaled group Lasso
• Statistical optimization in high dimensions
• A universal expectation bound on empirical projections of deformed random matrices
• Channel estimation for finite scatterers massive multi-user MIMO system
• scientific article; zbMATH DE number 7626769 (Why is no real title available?)
• scientific article; zbMATH DE number 7625155 (Why is no real title available?)
• Optimal eigenvalue approximation via sketching
• Communication-efficient distributed covariance sketch, with application to distributed PCA
• The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding
• From low- to high-dimensional moments without magic
• High-dimensional covariance matrix estimation with missing observations
• Applied harmonic analysis and data science. Abstracts from the workshop held November 28 -- December 4, 2021 (hybrid meeting)
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Pivotal variable detection of the covariance matrix and its application to high-dimensional factor models
• How close is the sample covariance matrix to the actual covariance matrix?
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• Parisi formula, disorder chaos and fluctuation for the ground state energy in the spherical mixed \(p\)-spin models
• Multichannel deconvolution with long-range dependence: a minimax study
• Efficient, certifiably optimal clustering with applications to latent variable graphical models
• The expected norm of a sum of independent random matrices: an elementary approach

This page was built for publication: Spectral norm of products of random and deterministic matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q718893)