Almost maximally rigid non-closedness conjecture

At least 7 years old · documented by

Let LS⁡n(r,s)\operatorname{LS}_n(r,s) denote the set of matrices that can be written as the sum of an n×nn\times n matrix of rank at most rr and an n×nn\times n matrix with at most ss nonzero entries. Almost maximally rigid non-closedness conjecture. The low-rank plus sparse set LS⁡n(r,s)\operatorname{LS}_n(r,s) is not closed provided

n≥r+(s+1)1/2,n \geq r + (s+1)^{1/2},

for s∈[1,(n−1)2−1]s \in [1,(n-1)^2-1] and r∈[1,n−2]r \in [1,n-2]. This would generalize the established non-closedness of LS⁡3(1,3)\operatorname{LS}_3(1,3) to the highest sparsities allowed by the stated bounds, but the general case remains open.

References

Primary source

Jared Tanner, Andrew Thompson and Simon Vary, “Matrix rigidity and the ill-posedness of Robust PCA and matrix completion”, arXiv:1811.05919 (2019).

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.