# Jointly low-rank and bisparse recovery: Questions and partial answers

Type
Publication
Analysis and Applications

Abstract: 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 ≍ r s łn(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 ≍ r s^γ łn(en/s)$$ for some exponent $$γ > 0$$. We show that this is feasible for $$γ = 2$$, and that the proposed analysis cannot cover the case $$γ łeq 1$$. The precise value of the optimal exponent $$γ ın [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.