Sharp least-singular-value bounds for independent random tensor columns
Fix $K > 0$. For each $n$ let $d = d(n) \ge 1$ with $d = o\bigl(\sqrt{n / \log n}\bigr)$, and for $\varepsilon \in (0, 1/2]$ put $N = n^d$ and $m = \lfloor (1 - \varepsilon) N \rfloor$. Let $x_{ik} \in \mathbb{R}^n$ ($1 \le i \le m$, $1 \le k \le d$) be random vectors whose coordinates, over all $i$ and $k$, are independent, with mean zero, variance one and subgaussian norm $\|\cdot\|_{\psi_2}$ at most $K$, and let $A$ be the $N \times m$ matrix whose $i$th column is $x_{i1} \otimes \cdots \otimes x_{id}$. For $d = 1$, Rudelson and Vershynin's bound gives $s_{\min}(A) \gtrsim \varepsilon \sqrt{n}$. Vershynin proved that if $C d^2 \log(n)/n \le \varepsilon \le 1/2$, then $s_{\min}(A) \ge \sqrt{\varepsilon}/2$ with probability at least $1 - 2\exp(-c \varepsilon n / d)$, where $c, C > 0$ depend only on $K$.
Problem. Is there a constant $c_K > 0$, independent of $n$, $d$ and $\varepsilon$, such that $$\mathbb{P}\bigl\{s_{\min}(A) \ge c_K \varepsilon n^{d/2}\bigr\} \to 1 \quad (n \to \infty)$$ for every fixed $\varepsilon \in (0, 1/2]$, every such sequence $d(n)$ and every such choice of coordinate distributions?
Source: Vershynin (2020), Section 1.5, who asks whether his bound can be improved to εn^{d/2}; stated in this form by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- ST
- Keywords
- AIM Open Applied Problems, random matrices, random tensors, singular values
References
@article{vershynin2020,
author = {Vershynin, Roman},
title = {Concentration inequalities for random tensors},
journal = {Bernoulli},
volume = {26},
number = {4},
year = {2020},
pages = {3139--3162},
doi = {10.3150/20-BEJ1218},
eprint = {1905.00802},
archivePrefix = {arXiv},
}
@article{rudelson2009,
author = {Rudelson, Mark and Vershynin, Roman},
title = {Smallest singular value of a random rectangular matrix},
journal = {Comm. Pure Appl. Math.},
volume = {62},
number = {12},
year = {2009},
pages = {1707--1739},
doi = {10.1002/cpa.20294},
}
@misc{aim-tensor-singular-value,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Sharp least-singular-value bounds for independent random tensor columns}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/c9929805cece044705abaaebe1cebddac1ba11a6/problems/562-tensor-singular-value.md},
note = {Entry 562 at commit c992980, 2026-10-05},
}
Resolution claims
Let \(A\) have \(m=\lfloor(1-\varepsilon)n^d\rfloor\) independent columns, each the tensor product of \(d\) random vectors in \(\R^n\). All scalar coordinates are independent, centered, of variance one, and have subgaussian norm at most \(K\). We prove that, for every fixed \(\varepsilon\in(0,1/2]\) and every integer sequence \(d=o(\sqrt{n/\log n})\), the least singular value is at least \(c_K\varepsilon n^{d/2}\) with probability tending to one. The …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Open → Solution claimed | The registry's curators | Least singular values of independent random tensor columns v1 recorded from AIM @ 24edaad, paper/main.pdf. |
| 2026-10-13 | Needs verification → Open | The registry's curators | Listed as open: the complete solution claimed in AIM pull request #76 (12 October 2026) has not been reviewed there yet. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00274, "Sharp least-singular-value bounds for independent random tensor columns", clopen.solutions.