2019/02/13 by Foucart, Simon, Gribonval, Rémi, Jacques, Laurent +1
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.1902.04731
We investigate the problem of recovering jointly r-rank and s-bisparse matrices from as few linear measurements as possible, considering arbitrary measurements as well as rank-one measurements. In both cases, we show that m \asymp r s ln(en/s) measurements make the recovery possible in theory, meaning via a nonpractical algorithm. In case of arbitrary measurements, we investigate the possibility of achieving practical recovery via an iterative-hard-thresholding algorithm when m \asymp r sγln(en/s) for some exponent γ> 0. We show that this is feasible for γ= 2, and that the proposed analysis cannot cover the case γ≤ 1. The precise value of the optimal exponent γ∈ [1,2] is the object of a question, raised but unresolved in this paper, about head projections for the jointly low-rank and bisparse structure. Some related questions are partially answered in passing. For rank-one measurements, we suggest on arcane grounds an iterative-hard-thresholding algorithm modified to exploit the nonstandard restricted isometry property obeyed by this type of measurements.