Questions tagged [compressed-sensing]
The compressed-sensing tag has no usage guidance.
23
questions with no upvoted or accepted answers
4
votes
0
answers
140
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
4
votes
0
answers
772
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,353
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
0
answers
43
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
2
votes
0
answers
98
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 ...
- 847
2
votes
1
answer
225
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
2
votes
0
answers
80
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
2
votes
0
answers
597
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
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
1
vote
1
answer
134
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,726
1
vote
0
answers
54
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,726
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,816
1
vote
0
answers
142
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?
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
816
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
1
vote
0
answers
149
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
473
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
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 ...
- 800
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,493
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,816
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
0
answers
146
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
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