Optimal and algorithmic norm regularization of random matrices

DOI10.1090/PROC/15964MaRDI QIDQ5096658zbMATH OpenOpenAlexFDO

Authors Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Publication date 18 August 2022

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

zbMATH Keywords

algorithmnormrandom matrix

Mathematics Subject Classification ID

Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60) Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20)

Abstract: Let $A$ be an $nimesn$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$. We present a deterministic polynomial time algorithm which, with probability at least $1-2exp(-Omega(epsilonn))$ in the choice of $A$, finds an $epsilonnimesepsilonn$ sub-matrix such that zeroing it out results in $widetildeA$ with [|widetilde{A}| = Oleft(sqrt{n/epsilon} ight).] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for $A$ a symmetric $nimesn$ random matrix whose upper-diagonal entries are i.i.d. with mean $0$ and variance $1$.

Recommendations

• Constructive regularization of the random matrix norm
• Norms of random matrices: local and global problems
• Sampling from large matrices
• Some estimates of norms of random matrices
• Spectral norm of random matrices

Cites work

• A note on the largest eigenvalue of a large dimensional sample covariance matrix
• Column subset selection, matrix factorization, and eigenvalue optimization
• Concentration and regularization of random graphs
• Constructive regularization of the random matrix norm
• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• Nearly tight oblivious subspace embeddings by trace inequalities
• Non-asymptotic theory of random matrices: extreme singular values
• Norms of random matrices: local and global problems
• On the limit of the largest eigenvalue of the large dimensional sample covariance matrix
• Probability Inequalities for Sums of Bounded Random Variables
• Spectral techniques applied to sparse random graphs
• The Expected Norm of Random Matrices

Cited in

(7)

• Norms of random matrices: local and global problems
• Cauchy noise loss for stochastic optimization of random matrix models via free deterministic equivalents
• Norms of random submatrices and sparse approximation
• Regularization of Non-Normal Matrices by Gaussian Noise
• scientific article; zbMATH DE number 4211377 (Why is no real title available?)
• A direct method to Frobenius norm-based matrix regression
• Constructive regularization of the random matrix norm

This page was built for publication: Optimal and algorithmic norm regularization of random matrices

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