Questions tagged [compressed-sensing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1 vote
0 answers
61 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 $...
user avatar
  • 5,830
0 votes
0 answers
58 views

sharp $l_{\infty}$-bounds for the LASSO estimator

I have a question regarding sharp $l_{\infty}$-bounds for the LASSO estimator. The linear model is $$y=X\theta^*+W,$$ where $X\in\mathbb{R}^{n\times p}$ a deterministic matrix (or a probabilistic one ...
user avatar
7 votes
4 answers
390 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 $...
user avatar
  • 5,830
2 votes
1 answer
60 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}...
user avatar
2 votes
0 answers
79 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 ...
user avatar
1 vote
0 answers
50 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-...
user avatar
  • 5,830
0 votes
0 answers
64 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\...
user avatar
  • 1,293
3 votes
0 answers
193 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 ...
user avatar
  • 31
1 vote
1 answer
154 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{...
user avatar
1 vote
0 answers
78 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 ...
user avatar
  • 1,748
1 vote
1 answer
80 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 ...
user avatar
  • 323
3 votes
1 answer
242 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 $\...
user avatar
0 votes
0 answers
115 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. ...
user avatar
  • 1,748
1 vote
1 answer
124 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....
user avatar
  • 2,006
1 vote
0 answers
131 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?
user avatar
2 votes
0 answers
76 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 ...
user avatar
  • 21
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 ...
user avatar
0 votes
1 answer
66 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 ...
user avatar
1 vote
0 answers
69 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 ...
user avatar
1 vote
0 answers
690 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 {\...
user avatar
  • 857
2 votes
1 answer
79 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 $...
user avatar
1 vote
0 answers
126 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 ...
user avatar
1 vote
0 answers
417 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)...
user avatar
  • 221
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 \...
user avatar
  • 857
1 vote
2 answers
607 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 ...
user avatar
  • 505
1 vote
1 answer
598 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\...
user avatar
  • 1,095
2 votes
0 answers
491 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(...
user avatar
3 votes
1 answer
82 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 ...
user avatar
  • 623
2 votes
1 answer
243 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 ...
user avatar
  • 21
5 votes
1 answer
466 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 ...
user avatar
  • 183
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.
user avatar
3 votes
1 answer
212 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 ...
user avatar
  • 797
4 votes
0 answers
127 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 ...
user avatar
3 votes
1 answer
278 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 ...
user avatar
  • 131
4 votes
1 answer
613 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 \{...
user avatar
  • 797
1 vote
1 answer
495 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 ...
user avatar
  • 189
-1 votes
2 answers
532 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 ...
user avatar
  • 453
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 ...
user avatar
1 vote
1 answer
210 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 ...
user avatar
  • 555
0 votes
1 answer
487 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 ...
user avatar
  • 11
1 vote
0 answers
262 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 ...
user avatar
  • 760
1 vote
1 answer
201 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. ...
user avatar
  • 11
2 votes
3 answers
390 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 ...
user avatar
  • 21
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)...
user avatar
  • 129
4 votes
0 answers
768 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 ...
user avatar
  • 2,303