跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2405.01517 · v3

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries

首次提交 2024-05-03 01:48
版本更新 2026-11-16 03:34
雷达观测 2026-11-17 17:12
arXiv ↗PDF ↗

摘要

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 involving a hierarchical εε-nets 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 include new smoothed analysis guarantees for subspace clustering 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.

作者备注:A previous version of this manuscript contained an error. This version of the manuscript corrects the error, and is able to recover the main theorem and the applications to certifying subspace entanglement and subspace clustering. The previously claimed application to power-sum decomposition is not established

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-16 03:34 · 最新观测版本

New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries

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 involving a hierarchical εε-nets 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 include new smoothed analysis guarantees for subspace clustering 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.

查看此版本解读 →查看此版本原文 ↗