Restricted-isometry conjecture for truncated sparse approximation properties

From papers

Let AA be a measurement matrix, let kk be a positive integer, and let t(0,4/3)t\in(0,4/3). Write δtk\delta_{tk} for the restricted 2-isometry constant of order tktk. The (l2,l1)(l_2,l_1)-l2l_2 sparse approximation property and the (l2,l1)(l_2,l_1)-Dantzig selector sparse approximation property are the properties of order kk defined for the corresponding truncated minimization models.

Restricted-isometry conjecture. If AA has restricted 2-isometry property of order tktk with

δtk<(4t)/t,\delta_{tk}<(4-t)/t,

then AA satisfies (l2,l1)(l_2,l_1)-l2l_2 sparse approximation property of order kk with certain constants 0<γ<10<\gamma<1 and 0<D3<0<D_3<\infty, and (l2,l1)(l_2,l_1)-Dantzig selector sparse approximation property of order kk with certain constants 0<γ<10<\gamma<1 and 0<D4<0<D_4<\infty.

This conjecture proposes a sufficient restricted-isometry condition for stable sparse approximation under both truncated l2l_2 minimization and truncated Dantzig-selector minimization in the previously unresolved range 0<t<4/30<t<4/3.

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

Wengu Chen and Peng Li, “Truncated Sparse Approximation Property and Truncated q-Norm Minimization”, arXiv:1806.10788 (2018).

Solutions 0

No solutions have been posted yet.