Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [compressed-sensing]

The tag has no usage guidance.

1
vote
1answer
101 views

Two theorems about incoherence

These are two theorems I have heard being referred to in "folklore" but I cant find the proofs for these in any compressed sensing or high-dimensional probability reviews (like, https://www.math.uci....
1
vote
0answers
94 views

Restricted isometry property for Subgaussian matrices with non-diagonal covariance?

I was wondering if there were any results on whether the restricted isometry property held for Subgaussian or Gaussian random matrices that had covariance matrices that were not completely diagonal?
2
votes
0answers
59 views

Statistical properties from the projection on Hadamard matrix

I am using Hadamard matrix to generate the measurement matrix in compressive sensing for signal acquisition. Consider all the rows except the first row, which consists of all 1's, as a candidate for ...
0
votes
0answers
33 views

Question about a systematic row reduction algorithm for compressive sensing

Suppose a ''brute-force'' algorithm is designed to systematically select from the first $n$ columns of an $m \times (n+1),$ $m<n$ augmented matrix $G$ representing a consistent underdetermined ...
0
votes
1answer
53 views

Can there be underdetermined linear systems whose set of minimal support solutions is infinite?

Let $A \in \mathbb{F}^{m \times n},$ $m<n,$ and let $b \in \mathbb{F}^{m \times n}$ be such that the system $Ax=b$ is consistent. Does it follow that the set $X$ of minimal support solutions of ...
1
vote
0answers
63 views

Proving an Algorithm that generates minimal $\|x\|_0$ for the underdetermined system $Ax=b$

Let $A \in \mathbb {F}^{m \times n}$ with $m< n,$ $b \in \mathbb{F}^m$ and let $x$ be unknown in $\mathbb{F}^n.$ Assume $0<p<1.$ Then $$\arg \min\limits_{x: Ax=b} \|x\|_0 = \lim\limits_{p \to ...
1
vote
0answers
469 views

L0 norm compressed sensing vs L1 norm compressed sensing

Suppose we have an very efficient way to perform L0 norm compressed vs L1 norm compressed sensing. Specifically: L0 norm compressed sensing is: $$\eqalign{ & \min \quad {x^T}Qx + {b^T}x + \mu {\...
2
votes
1answer
68 views

NP-Hardness of finding minimal-support solutions of underdetermined systems over any field

Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $...
1
vote
0answers
99 views

NP-Hardness of Underdetermined Systems over $F_2$ implies the same for $F_{p^q}$

Assume that the yes-no problem of whether $x' \in F_{p^q}^{n}$ is a minimal support solution for a consistent underdetermined system $Ax=b,$ $A \in F_{p^q}^{m \times n}, b \in F_{p^q}^n$ is an NP-hard ...
1
vote
0answers
259 views

psd condition for matrix completion

The nuclear norm minimization for the matrix completion problem is given by \begin{align} \textrm{minimize } \quad &\|X\|_{*}\\ \textrm{subject to } \quad & X_{ij}=M_{ij} \quad \forall (i,j)...
0
votes
0answers
130 views

choosing regularization constant in compressive sensing

Given a compressive sensing formulation, $$\left\| {Ax - b} \right\|_2^2 + \mu {\left\| x \right\|_1}$$ And given curves (a) $\left\| {Ax - b} \right\|_2^2$ plotted against $\log \left( \mu \...
1
vote
2answers
355 views

Concentration of matrix norms under random projection.

Let X be a given matrix of dimension $p \times q$. Let $G$ be a $s \times p$ dimensional matrix of standard normal/Gaussian random variables. Are there cases where one can been able to quantify $P_G ...
1
vote
1answer
336 views

Restricted Isometry Property for Discrete Fourier Transform Matrix

I was wondering if the Restricted Isometry Property holds for Discrete Fourier Transform. In particular, I am interested in whether a subsampled DFT matrix has such property. Let$W \in \mathbb{C}^{d\...
1
vote
0answers
274 views

Can I use proximal algorithms on complex real-valued functions?

There is a plethora of literature in proximal operators and proximal optimization algorithms specially for Compressive sensing. A proximal operator is defined as \begin{equation} \operatorname{prox}_f(...
3
votes
1answer
74 views

Vanishing Restricted Isometric Constant

In compressed sensing, we are interested in the restricted isometry property. Suppose the design matrix is $n$ by $p$, consisting of $np$ iid $\mathcal{N}(0, 1/n)$ entries. Assume both $n$ and $p$ are ...
2
votes
1answer
180 views

Phase of the inner product between the elements of an ETF

I am doing research in compressive sampling for Cognitive Radio applications. While working on a project I came across with the following question: Is there any research about the phase of inner ...
5
votes
1answer
378 views

Finding sparsest solution of a linear system

I want to find the solution with most zero-components for the following problem: $Ax=b$ for $A\in \mathbb{R}^{k\times n}, b \in \mathbb{R}^{k},k<n$, where $x$ is real and has no additional ...
3
votes
1answer
1k views

Open problems in compressed sensing

What are the main open problems in compressed sensing? I am interested in theoretical as well as in numerical point of view.
3
votes
1answer
176 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
117 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 ...
2
votes
0answers
172 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 ...
4
votes
1answer
548 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
389 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
479 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
159 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
195 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
481 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
254 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 ...
1
vote
1answer
181 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
375 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
896 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 (rectangular)...
4
votes
0answers
757 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 ...