Polynomial upper-bound conjecture for the smallest singular value of submatrices

About 13 years old · traced to

Let F=[g1,g2,…,gn+k]F=[g_1,g_2,\dots,g_{n+k}] be an n×(n+k)n\times(n+k) matrix, and define

τ=min⁡{σn(FS):S⊂{1,…,n+k}, ∣S∣=n}.\tau=\min\{\sigma_n(F_S):S\subset\{1,\dots,n+k\},\ |S|=n\}.

Assume that ∥gj∥≤1\|g_j\|\leq1 for every jj. Polynomial upper-bound conjecture. There exists a constant C=C(k)C=C(k) such that

τ≤Cnk−12.\tau\leq\frac{C}{n^{k-\frac12}}.

For k=1k=1, the source notes a previously established upper bound of order n−3/2n^{-3/2}; the conjecture proposes the corresponding order n−(k−1/2)n^{-(k-1/2)} for general fixed kk.

References

Primary source

Radu Balan and Yang Wang, “Invertibility and Robustness of Phaseless Reconstruction”, arXiv:1308.4718 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.