What is the Largest Sparsity Pattern that Can Be Recovered by 1-Norm Minimization?
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns
We study the problem of consistently recovering the sparsity pattern of a regression parameter vector from correlated observations governed by deterministic missing data patterns using Lasso. We consider the case in whic…
ImputationExploring the effects of Lx-norm penalty terms in multivariate curve resolution methods for resolving LC/GC-MS data
There are different problems for resolution of complex LC-MS or GC-MS data, such as the existence of embedded chromatographic peaks, continuum background and overlapping in mass channels for different components. These p…
An Inequality with Applications to Structured Sparsity and Multitask Dictionary Learning
From concentration inequalities for the suprema of Gaussian or Rademacher processes an inequality is derived. It is applied to sharpen existing and to derive novel bounds on the empirical Rademacher complexities of unit …
Dictionary LearningBinary Fused Compressive Sensing: 1-Bit Compressive Sensing meets Group Sparsity
We propose a new method, {\it binary fused compressive sensing} (BFCS), to recover sparse piece-wise smooth signals from 1-bit compressive measurements. The proposed algorithm is a modification of the previous {\it binar…
Compressive SensingThresholding for Top-k Recommendation with Temporal Dynamics
This work focuses on top-k recommendation in domains where underlying data distribution shifts overtime. We propose to learn a time-dependent bias for each item over whatever existing recommendation engine. Such a bias l…
Recommendation Systems