Jointly Low-Rank and Bisparse Recovery: Questions and Partial Answers - Archive ouverte HAL Access content directly
Journal Articles Analysis and Applications Year : 2020

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

(1) , (2, 3) , (4) , (5)
1
2
3
4
5
Simon Foucart
• Function : Author
Rémi Gribonval
Laurent Jacques
• Function : Author
• PersonId : 870853
Holger Rauhut
• Function : Author
• PersonId : 858949

#### 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.

#### Domains

Computer Science [cs] Signal and Image Processing

### Dates and versions

hal-02062891 , version 1 (11-03-2019)
hal-02062891 , version 2 (25-10-2019)

### Identifiers

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

### Cite

Simon Foucart, Rémi Gribonval, Laurent Jacques, Holger Rauhut. Jointly Low-Rank and Bisparse Recovery: Questions and Partial Answers. Analysis and Applications, 2020, 18 (01), pp.25--48. ⟨10.1142/S0219530519410094⟩. ⟨hal-02062891v2⟩

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

176 View