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]

Much of the existing literature in sparse recovery is concerned with the following question: given a sparsity pattern and a corresponding regularizer, derive conditions on the dictionary under which exact recovery is possible. In this paper, we study the opposite question: given a dictionary and the `1-norm regularizer, find the largest sparsity pattern that can be recovered. We show that such a pattern is described by a mathematical object called a “maximum abstract simplicial complex,” and provide two different characterizations of this object: one based on extreme points and the other based on vectors of minimal support. 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 case of incidence matrices, we show that the largest sparsity pattern that can be recovered is determined by the set of simple cycles of the graph. As a byproduct, we show that standard sparse recovery can be certified in polynomial time, although this is known to be NP- hard for general matrices. In the case of the partial discrete Fourier transform, our characterization of the largest sparsity pattern that can be recovered requires the unknown signal to be real and its dimension to be a prime number.

@article{kzvrm2021tit,
  abstract = {Much of the existing literature in sparse recovery is concerned with the following question: given a sparsity pattern and a corresponding regularizer, derive conditions on the dictionary under which exact recovery is possible. In this paper, we study the opposite question: given a dictionary and the `1-norm regularizer, find the largest sparsity pattern that can be recovered. We show that such a pattern is described by a mathematical object called a "maximum abstract simplicial complex," and provide two different characterizations of this object: one based on extreme points and the other based on vectors of minimal support. 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 case of incidence matrices, we show that the largest sparsity pattern that can be recovered is determined by the set of simple cycles of the graph. As a byproduct, we show that standard sparse recovery can be certified in polynomial time, although this is known to be NP- hard for general matrices. In the case of the partial discrete Fourier transform, our characterization of the largest sparsity pattern that can be recovered requires the unknown signal to be real and its dimension to be a prime number.},
  author = {Kaba, Mustafa Devrim and Zhao, Mengnan and Vidal, Rene and Robinson, Daniel R. and Mallada, Enrique},
  bdsk-url-3 = {https://doi.org/10.1109/TIT.2021.3067280},
  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}
}