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

From papers

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 gj1\|g_j\|\leq1 for every jj. Polynomial upper-bound conjecture. There exists a constant C=C(k)C=C(k) such that

τCnk12.\tau\leq\frac{C}{n^{k-\frac12}}.

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

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.