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 ...
- 111
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., $\|\...
- 261
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$...
- 21
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 $...
- 6,556
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
$...
- 6,556
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}...
- 6,812
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 ...
- 827
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-...
- 6,556
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\...
- 1,471
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 ...
- 131
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{...
- 21
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,796
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 ...
- 381
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
$\...
- 33
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,796
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....
- 2,136
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 ...
- 21
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 ...
- 259
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 ...
- 259
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 ...
- 259
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 {\...
- 867
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 $...
- 259
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 ...
- 259
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)...
- 221
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 \...
- 867
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 ...
- 545
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\...
- 1,117
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(...
- 345
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 ...
- 753
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 ...
- 21
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 ...
- 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.
- 6,812
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 ...
- 807
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 ...
- 41
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 ...
- 131
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 \{...
- 807
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 ...
- 189
-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 ...
- 453
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 ...
- 87
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 ...
- 615
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 ...
- 11
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 ...
- 770
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. ...
- 11
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 ...
- 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)...
- 129
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 ...
- 2,313