Spectral norm of products of random and deterministic matrices

DOI10.1007/S00440-010-0281-ZzbMATH Open1235.60009arXiv0812.2432OpenAlexW2047265165MaRDI QIDQ718893FDOQ718893

Roman Vershynin

Publication date: 27 September 2011

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

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.

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)

Cites Work

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

Cited In (41)

• LASSO risk and phase transition under dependence
• On Approximating Matrix Norms in Data Streams
• A new error in variables model for solving positive definite linear system using orthogonal matrix decompositions
• Title not available (Why is that?)
• Probably certifiably correct \(k\)-means clustering
• Generalized Low-Rank Plus Sparse Tensor Estimation by Fast Riemannian Optimization
• On the non-asymptotic concentration of heteroskedastic Wishart-type matrix
• Provable Phase Retrieval with Mirror Descent
• Title not available (Why is that?)
• Asymptotic geometric analysis: achievements and perspective
• Title not available (Why is that?)
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Non-asymptotic bounds for the \(\ell_{\infty}\) estimator in linear regression with uniform noise
• Random matrix theory in statistics: a review
• Frequent directions: simple and deterministic matrix sketching
• Eigenvectors of random matrices: A survey
• Lower bounds for the smallest singular value of structured random matrices
• Invertibility of sparse non-Hermitian matrices
• 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.
• Universality and sharp matrix concentration inequalities
• ROP: matrix recovery via rank-one projections
• 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
• Channel estimation for finite scatterers massive multi-user MIMO system
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal eigenvalue approximation via sketching
• 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
• 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
• High-dimensional covariance matrix estimation with missing observations
• Pivotal variable detection of the covariance matrix and its application to high-dimensional factor models
• Bias-Adjusted Spectral Clustering in Multi-Layer Stochastic Block Models
• How close is the sample covariance matrix to the actual covariance matrix?
• 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

Recommendations

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

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)