# Questions tagged [compressed-sensing]

The compressed-sensing tag has no usage guidance.

43
questions

**0**

votes

**0**answers

159 views

### Computing matrix product (A x) via unrelated matrix Q [closed]

Given a matrix vector product that is difficult (e.g., dense, unstructured, huge, etc) $A x$ and an oracle $Q$ that can quickly calculate $Qv$ for arbitrary input $v$ (for some definition of "...

**1**

vote

**1**answer

55 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

66 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

47 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

57 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

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

**1**

vote

**1**answer

76 views

### Basis pursuit algorithms for exponentially large matrices?

Are there any efficient algorithms/heuristics for basis pursuit for exponentially large matrices?
That is $\arg\min_x\lVert x \rVert_0$ subject to $y = Ax$, where $A$ is an exponentially large matrix ...

**1**

vote

**0**answers

77 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

73 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

218 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

97 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

109 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

128 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

74 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

38 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

64 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

68 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

609 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

78 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

115 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

362 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

144 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

516 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

505 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

438 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

80 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

226 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

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

**3**

votes

**1**answer

203 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

**0**answers

124 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

**1**answer

222 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

585 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

482 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

511 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

165 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

202 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

486 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

259 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

191 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

385 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

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