1 paper accepted to TIT

by

Our paper on sparse recovery by 1-norm minimization [1] has been accepted to IEEE Transactions on Information Theory!

[1] [doi] M. D. Kaba, M. Zhao, R. Vidal, D. R. Robinson, and E. Mallada, “What is the Largest Sparsity Pattern that Can Be Recovered by 1-Norm Minimization?,” IEEE Transactions on Information Theory, vol. 67, iss. 5, pp. 3060-3074, 2021.
[Bibtex] [Abstract] [Download PDF]

We propose a new framework for studying the recovery of signals with structured sparsity patterns via $l_1$-minimization. We achieve this by generalizing the well-known nullspace property for sparse recovery. We show that for each dictionary there is a maximum sparsity pattern—described by a mathematical object called an abstract simplicial complex—that can be recovered via $l_1$-minimization. We provide two different characterizations of this maximum sparsity pattern. In addition, we show how this new framework is useful in the study of sparse recovery problems when the dictionary takes the form of a graph incidence matrix or a partial Discrete Fourier Transform. In both cases we successfully characterize the collection of all support sets for which exact recovery via $l_1$-minimization is possible. When the dictionary is an incidence matrix, we show that the success of exact recovery can be certified in polynomial time, although this is known to be NP-hard for general matrices.

@article{kzvrm2021tit,
  abstract = {We propose a new framework for studying the recovery of signals with structured sparsity patterns via $l_1$-minimization. We achieve this by generalizing the well-known nullspace property for sparse recovery. We show that for each dictionary there is a maximum sparsity pattern---described by a mathematical object called an abstract simplicial complex---that can be recovered via $l_1$-minimization.  We provide two different characterizations of this maximum sparsity pattern. In addition, we show how this new framework is useful in the study of sparse recovery problems when the dictionary takes the form of a graph incidence matrix or a partial Discrete Fourier Transform. In both cases we successfully characterize the collection of all support sets for which exact recovery via $l_1$-minimization is possible. When the dictionary is an incidence matrix, we show that the success of exact recovery can be certified in polynomial time, although this is known to be NP-hard for general matrices.},
  author = {Kaba, Mustafa Devrim and Zhao, Mengnan and Vidal, Rene and Robinson, Daniel R. and Mallada, Enrique},
  doi = {10.1109/TIT.2021.3067280},
  grants = {AMPS:1736448;CAREER-1752362},
  journal = {IEEE Transactions on Information Theory},
  month = {5},
  number = {5},
  pages = {3060-3074},
  record = {early access Mar. 2021, accepted Jan. 2021, revised Apr. 2020, submitted Oct. 2019},
  title = {What is the Largest Sparsity Pattern that Can Be Recovered by 1-Norm Minimization?},
  url = {https://mallada.ece.jhu.edu/pubs/2021-TIT-KZVRM.pdf},
  volume = {67},
  year = {2021}
}