Questions tagged [compressed-sensing]
The compressed-sensing tag has no usage guidance.
50
questions
0
votes
1
answer
54
views
Logan's theorem in compressed sensing
In some research papers in the nuclear magnetic resonance field Ref:, Logan's theorem is used to provide a justification for randomized sampling of free induction decay curves which are converted to ...
- 790
2
votes
1
answer
245
views
Usage and origin of the terms dictionary and atom in compressed sensing
In compressed sensing two terms or perhaps fancy word are frequently encountered. One is the dictionary and the other is atom. The dictionary is the matrix and its columns are called "atoms" ...
- 790
0
votes
0
answers
34
views
Efficient compression techniques for low-rank matrix $A$ to maintain multiplication compatibility？
Suppose we have a large low-rank matrix $A$ and an input matrix $X$ (where $X$ is a tall, skinny matrix). We need to compute the product $AX$. To reduce computational cost and data transfer when ...
- 25
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
75
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., $\|\...
- 311
2
votes
0
answers
44
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
142
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,824
7
votes
4
answers
463
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,824
2
votes
1
answer
77
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,922
2
votes
0
answers
99
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 ...
- 897
1
vote
0
answers
55
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,824
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,503
3
votes
0
answers
204
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
230
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,826