# Questions tagged [compressed-sensing]

The compressed-sensing tag has no usage guidance.

47
questions

1
vote

0
answers

55
views

### Compressed sensing / compressive sensing: what is the lower bound on dimension of the measurement matrix?

I am looking for references discussing the formal requirements for the dimension $m$ of the "measurement" mixing matrix in compressive sensing (as in ${\bf y} = M {\bf x}$ where ${\bf y} \in ...

0
votes

1
answer

68
views

### Probability of accurate sparse recovery

Suppose $\mathbf{A}_{k\times n}$ ($k<n$) is a matrix whose entries are generated i.i.d. from Gaussian distribution and $\mathbf{s}_{n\times 1}$ is a sparse vector with $m$ sparsity (i.e., $\|\...

2
votes

0
answers

41
views

### Combining SVD subspaces for low dimensional representations

Suppose we have matrix $A$ of size $N_t \times N_m$, containing $N_m$ measurements corrupted by some (e.g. Gaussian) noise. An SVD of this data $A = U_AS_A{V_A}^T$ can reveal the singular vectors $U_A$...

1
vote

1
answer

122
views

### Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$

Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $...

7
votes

4
answers

449
views

### What does $\mathbb E_V \max_{x \in V,\,\|x\|=1} x^T Ax$ evaluate to when $V$ is random $k$-dim suspace of $\mathbb R^n$ and $A$ is fixed psd matrix?

Let $G_{k,n}$ be the grassmannian of $k$-dimensional vector spaces of $\mathbb R^n$. By the Courant–Fisher characterization, the $k$th largest eigenvalue of an $n \times n$ psd matrix $A$ is given by
$...

2
votes

1
answer

70
views

### Column subset selection with least angle optimization

Given a matrix $A$ I need to select a "representative" subset of its columns so that the each non-selected column is as close as possible to a selected one.
Formally:
Given $A \in \mathbb{R}...

2
votes

0
answers

95
views

### Sparse signal recovery (nonlinear case)

Let $K \subset \mathbb{R}^n$, it may be that $K$ is "very thin" (e.g. $K$ is a $k$-dimensional affine subset of $\mathbb{R}^n$, with $k \ll n$). I'm interested in the case where $K$ is ...

1
vote

0
answers

53
views

### Good lower-bound for $\inf_{x \in \Delta_n} \|Gx\|$ where $G$ is an $N \times n$ random matrix with iid entries from $\mathcal N(0,1/\sqrt{N})$

Let $G$ be an $N \times n$ random matrix with independent entries distributed according to a centered Gaussian with variance $1/\sqrt{N}$ and let $n/N = \lambda \in (0, 1)$. Let $\Delta_n$ be the $(n-...

0
votes

0
answers

65
views

### Matrix Dantzig selector with many constraints

We observe data from the model
$$
y_1=\mathcal{A}_1(X)+z_1\\
...\\
y_k=\mathcal{A}_k(X)+z_k\\
$$
where $X$ is an unknown $n\times n$ matrix with rank at most $r$, each $\mathcal{A}_i:\mathbb{R}^{n\...

3
votes

0
answers

202
views

### Compressed sensing for partitioning instead of recovery

Let $x_0 \in \mathbb{R}^{m}$ be a signal whose support $T_0 = \{ t \mid x_{0}(t) \neq 0\}$ is assumed to be of small cardinality. The recovery of $x_0$ from a small number of $n \ll m$ linear ...

2
votes

1
answer

211
views

### Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is
$$\begin{array}{ll} \underset{x \in \Bbb R^n}{\text{minimize}} & \lVert x \rVert_0\\ \text{...

1
vote

0
answers

81
views

### On sparse $0/1$ linear equations solvable with compressed sensing

If you have a system of $m$ linearly independent equations in $n$ variables with domain $0/1$ and we know there is at least one solution with at most $d$ variables to be $1$ then if $m$ at least a ...

1
vote

1
answer

86
views

### Additional structures for sparse recovery

The problem of sparse recovery using $l_1$ minimization is well known. Using random Gaussian matrices, we are able to achieve recovery with high probability in $O(k\log(d/k)$ measurements. It is ...

3
votes

1
answer

266
views

### Uniqueness of l1 minimization

Let $A \in \mathbb{R}^{m \times n}$.
Is it true that $$\min \limits_{Q \in \mathbb{R}^{n \times m}}|I - QA|_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to
$\...

0
votes

0
answers

122
views

### Does positivstellensatz and SOS proof system help here?

I have a system of $m$ homogeneous degree $2$ polynomial equations in $\mathbb Z[x_1,\dots,x_n]$ where $m=poly(n)$. Take
$$f_1(x_1,\dots,x_n)=0$$
$$\dots$$
$$f_m(x_1,\dots,x_n)=0$$
to be the system.
...

1
vote

1
answer

134
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

0
answers

136
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

0
answers

79
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

0
answers

40
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

1
answer

68
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

0
answers

71
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

0
answers

811
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

1
answer

99
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

0
answers

141
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

0
answers

460
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

0
answers

145
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

2
answers

766
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

1
answer

710
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\...

2
votes

0
answers

565
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

1
answer

85
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

1
answer

246
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

1
answer

490
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

1
answer

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.

4
votes

2
answers

268
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 \text{s.t.} \quad A x = b,$$
admits an $m$-sparse solution ...

4
votes

0
answers

138
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 ...

3
votes

1
answer

292
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

1
answer

621
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

1
answer

512
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

2
answers

564
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

0
answers

166
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

1
answer

214
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

1
answer

495
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

0
answers

265
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

1
answer

204
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

3
answers

400
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

3
answers

1k
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

0
answers

770
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 ...