Jointly Low-Rank and Bisparse Recovery: Questions and Partial Answers

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 \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^\gamma \ln(en/s)$ for some exponent $\gamma>0$. We show that this is feasible for $\gamma=2$ and that the proposed analysis cannot cover the case $\gamma \leq 1$. The precise value of the optimal exponent $\gamma \in [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 the 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-02062891
Contributor : Rémi Gribonval <>
Submitted on : Friday, October 25, 2019 - 3:43:29 PM
Last modification on : Monday, November 25, 2019 - 4:18:46 PM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02062891, version 2
  • ARXIV : 1902.04731

Citation

Simon Foucart, Rémi Gribonval, Laurent Jacques, Holger Rauhut. Jointly Low-Rank and Bisparse Recovery: Questions and Partial Answers. 2019. ⟨hal-02062891v2⟩

Share

Metrics

Record views

81

Files downloads

188