Truncated sparse approximation property and truncated q-norm minimization
This paper considers approximately sparse signal and low-rank matrix’s recovery via
truncated norm minimization min_x ∥xT ∥q and min_X ∥XT ∥Sq from noisy measurements. We first
introduce truncated sparse approximation property, a more general robust null space property,
and establish the stable recovery of signals and matrices under the truncated sparse approximation
property. We also explore the relationship between the restricted isometry property
and truncated sparse approximation property. And we also prove that if a measurement matrix
A or linear map A satisfies truncated sparse approximation property of order k, then the first
inequality in restricted isometry property of order k and of order 2k can hold for certain different
constants δk and δ2k, respectively. Last, we show that if δ_{s(k+jTcj)} <\sqrt{(s - 1)/s} for some
s ≥ 4/3, then measurement matrix A and linear map A satisfy truncated sparse approximation
property of order k. It should be pointed out that when T^c =\Phi, our conclusion implies that
sparse approximation property of order k is weaker than restricted isometry property of order sk.
关键词：
truncated norm minimization,
truncated sparse approximation property,
restricted isometry property,
sparse signal recovery,
low-rank matrix recovery,
Dantzig selector
