Tools for analyzing least singular values of smoothed random matrices
Paper Title:
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Published on:
2 May 2024
Primary Category:
Data Structures and Algorithms
Paper Authors:
Aditya Bhaskara,
Eric Evert,
Vaidehi Srinivas,
Aravindan Vijayaraghavan
Bullets
Key Details
Introduces hierarchical epsilon-nets technique to prove least singular value bounds
Gives statement about least singular values of higher-order lifts of smoothed matrices
Provides simpler proofs of existing smoothed analysis results
Handles more general families of random matrices
Gives new smoothed analysis guarantees for various open problems
Explore the topics in this paper
AI generated summary
Tools for analyzing least singular values of smoothed random matrices
The paper develops new techniques for lower bounding least singular values of random matrices with limited randomness. The entries depend on polynomials of underlying random variables. This setting captures key challenges in smoothed analysis. The tools involve hierarchical nets and reasoning about higher-order lifts of smoothed matrices. Applications include smoothed analysis guarantees for power sum decompositions, subspace clustering, and certifying robust entanglement.
Answers from this paper
You might also like
Matrix concentration with dependent summands and sharp leading-order term
Low-rank signal estimation from noisy tensors
Low-rank matrix optimization for sparse solutions
Recovering low-rank matrices robustly using volume minimization
Detecting a hidden signal in random noise matrices
Strong consistency of rank-constrained total least squares regression
Comments
No comments yet, be the first to start the conversation...
Sign up to comment on this paper