The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
61 views

Can one always find sparse solutions to an $\ell^1$-minimization problem?

Consider $A\in\mathbb{R}^{m \times N}$ and $b \in \mathbb{R}^m$, with $m<N$. Is it true that the optimization problem $$\min \|x\|_1 \quad s.t. \;\; A x = b,$$ admits an $m$-sparse solution in ...
4
votes
0answers
36 views

RIP of the sensing matrix sampled from biased Bernoulli distribution

I have recently worked toward applying compressed sensing technique to the case of which sensing matrix is sampled from biased Bernoulli distribution. So far I have found literature demonstrating ...
1
vote
0answers
62 views

Question in Wainwright's paper about signed support recovery in lasso

Sharp thresholds for high dimensional and noisy sparsity recovery using $l_1$ constrained quadratic programming (Lasso) This paper is about support recovery guarantees of the Lasso. I have an issue ...
3
votes
1answer
214 views

Can sparse matrices satisfy the Null Space Property?

Definition A matrix $A \in \mathbb{C}^{m \times N}$ with $m < N$ satisfies the Null Space Property (NSP) of order $s$ if $$\|x_S\|_1 < \|x_{\bar{S}}\|_1, \quad \forall x \in \ker A \setminus ...
1
vote
1answer
151 views

Restricted Isometry Property (Non Sparse Gaussian)

Let $x$ be a $N \times 1$ vector in $\mathbb{R}^{N}$ where $M$ components are zero and the remaining $N-M$ components are standard normal random variables. $x$ may not be sparse e.g. $M$ may be ...
-1
votes
2answers
440 views

Approximating a subspace by sampling a base without replacement

Let $X$ be a $p \times n$ matrix, with $p > n$. Now, suppose I sample $m < n$ columns from $X$ at random, without replacement. I would like to characterize the distance between the subspace ...
0
votes
0answers
97 views

Do the Eigenvectors find by use PCA on a set of data point, a good replacement for Random Projection when I later on use L1Magic to reconstruct the sparse vector?

Concretely if I use the first k eigenvectors find by PCA with a point set A,to project another sparse vector b to k dimension subspace, then use L1-magic to recover b. Will this be better than a ...
1
vote
1answer
148 views

Is there any alternative characterization of sparsity of a signal in compressed sensing

The starting assumption for compressed sensing (CS) is that the underlying signal is sparse in some basis, e.g., there are a maximum of $s$ non-zero Fourier-coefficients for an $s$-sparse signal. And ...
0
votes
1answer
170 views

$\ell_o$ Minimization (Minimizing the support of a vector)

I have been looking into the problem $\min: \|x \|_0$ subject to$: Ax=b$. $\|x \|_0$ is not a linear function and can't be solved as a linear (or integer) program in its current form. Most of my time ...
1
vote
0answers
221 views

Multiobjective semidefinite programming

Let $C$ be size $n \times n^{2}$. Let $B$ be size $2^{g(n)} \times n^{2}$ where $g(n) > n$. There is only one $\mathcal{1}$ per row of $C$ and remaining entries of $C$ are $\mathcal{0}$. $B$ is ...
0
votes
1answer
169 views

Recovering a matrix instead of a vector

It is known that given corrupt measurements $y = Af+e \in \mathbb{R}^m$ with $f \in \mathbb{R}^n$ and $\|f\|_0 < m < n$, one can recover $f$ exactly by solving a convex optimization problem. ...
2
votes
3answers
321 views

On a randomized version of compressive sensing

The compressive sensing theory of Candes and Tao (See http://en.wikipedia.org/wiki/Compressed_sensing) relies highly on the fact that the underlying data (such as a signal or an image) is sparse or ...
2
votes
3answers
596 views

Decomposing a discrete signal into a sum of rectangle functions

Hello mathoverflow community ! I have a simple question that seems to have a non trivial answer. Given a discrete one dimensional signal $w(x)$ defined in a finite range, and the boxcar ...
3
votes
0answers
701 views

Compressed Sensing with an Unusual Basis

I'm wondering if compressed sensing can be applied to a problem I have in the way I describe, and also whether it should be applied to this problem (or whether it's simply the wrong tool). I have a ...