## Abstract

We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by polynomials of a few underlying base random variables. This setting captures a core technical challenge for obtaining smoothed analysis guarantees in many algorithmic settings. Least singular value bounds often involve showing strong anti-concentration inequalities that are intricate and much less understood compared to concentration (or large deviation) bounds. First, we introduce a general technique for proving anti-concentration that uses well-conditionedness properties of the Jacobian of a polynomial map, and show how to combine this with a hierarchical ϵ-net argument to prove least singular value bounds. Our second tool is a new statement about least singular values to reason about higher-order lifts of smoothed matrices and the action of linear operators on them. Apart from getting simpler proofs of existing smoothed analysis results, we use these tools to now handle more general families of random matrices. This allows us to produce smoothed analysis guarantees in several previously open settings. These new settings include smoothed analysis guarantees for power sum decompositions and certifying robust entanglement of subspaces, where prior work could only establish least singular value bounds for fully random instances or only show non-robust genericity guarantees.

Original language | English (US) |
---|---|

Title of host publication | STOC 2024 - Proceedings of the 56th Annual ACM Symposium on Theory of Computing |

Editors | Bojan Mohar, Igor Shinkar, Ryan O�Donnell |

Publisher | Association for Computing Machinery |

Pages | 375-386 |

Number of pages | 12 |

ISBN (Electronic) | 9798400703836 |

DOIs | |

State | Published - Jun 10 2024 |

Event | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 - Vancouver, Canada Duration: Jun 24 2024 → Jun 28 2024 |

### Publication series

Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
---|---|

ISSN (Print) | 0737-8017 |

### Conference

Conference | 56th Annual ACM Symposium on Theory of Computing, STOC 2024 |
---|---|

Country/Territory | Canada |

City | Vancouver |

Period | 6/24/24 → 6/28/24 |

### Funding

Vaidehi Srinivas and Aravindan Vijayaraghavan were supported by the National Science Foundation under Grant Nos. CCF-1652491, ECCS-2216970. Vaidehi Srinivas was also supported by the North-western Presidential Fellowship. Aditya Bhaskara was supported by the National Science Foundation under Grant Nos. CCF-2008688 and CCF-2047288.

## Keywords

- least singular values
- matrix anticoncentration
- quantum entanglement
- random matrices
- smoothed analysis
- tensors
- unsupervised learning

## ASJC Scopus subject areas

- Software