6
votes
Accepted
Usage and origin of the terms dictionary and atom in compressed sensing
The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of &...
- 188k
3
votes
Accepted
Column subset selection with least angle optimization
You can solve this as a $k$-median (also known as $p$-median) problem. Each column is both a customer and a candidate facility location. Let $d_{c,f}$ denote the cost of assigning customer $c$ to ...
- 5,429
3
votes
Accepted
Uniqueness of l1 minimization
Yes, this is true. Since there exists a 'decoder' $Q$ which gives a value on the right hand side (close to or equal to) $\frac{1}{2}$, the pair $(A,Q)$ are $(\ell_\infty, \ell_1)$-instance optimal (...
- 3,209
2
votes
Two theorems about incoherence
Statement 1 is theorem 2.3 in Grassmannian Frames with Applications to Coding and Communication (2003):
$${\rm max}_{k\neq l}|\langle f_k,f_l\rangle|\geq \sqrt{\frac{N-d}{d(N-1)}}$$
for any set of $N$ ...
- 188k
2
votes
Accepted
Can there be underdetermined linear systems whose set of minimal support solutions is infinite?
If the minimal $\|x\|_0$ for a solution is $k$, any solution with $\|x\|_0 = k$ has support one of the ${n \choose k}$ subsets of $n$ with cardinality $k$.
The $m \times k$ submatrix $A_S$ of $A$ ...
- 54.2k
2
votes
Accepted
NP-Hardness of finding minimal-support solutions of underdetermined systems over any field
This proof looks correct to me. You don't have to worry about cancellations since the only way $z\in\mathbb{F}^N$ can have $|z|_0=m/3$ and $Az={\bf 1}$ is if $z$ is the indicator function for an ...
- 125
2
votes
Accepted
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?
In another answer, @dohmatob establishes the lower bound
$$
\alpha_k(A)\geq\frac{1}{n}\max\Big\{\operatorname{tr}(A),k\lambda_{\max}(A) \Big\}.
$$
In what follows, we show that this bound is near-...
- 7,633
2
votes
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?
Disclaimer. Here, I establish a somewhat trivial (and perhaps bad ?) lower-bound for $\alpha_k(A)$.
Note that $\alpha_k(A)$ is a nondecreasing function of $A$ (w.r.t the order: $X \ge Y \iff X - Y$ ...
- 6,853
1
vote
Is there a matrix that has the completely opposite effect of a Hadamard matrix?
I think the answer is no and here is my thought process:
We want a rotation matrix $R$ such that the elements in $RW$ are peakier in distribution (ie a column in $W$ with an outlier becomes more well ...
1
vote
Accepted
Probability of accurate sparse recovery
A good starting point is "Mathematics of sparsity (and a few other things)" by E. Candes, or a book on compressed sensing such as "A Mathematical Introduction to Compressive Sensing&...
- 1,724
1
vote
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?
As explained in the other answers, it is enough to study $\|\sqrt AX\|_{op}$
if $k<c n$ where $X$ has iid $N(0,1/n)$ entries.
I am adding an extra answer regarding the upper bounds, that is mostly ...
- 1,724
1
vote
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?
Short story: if $\log n \ll k < c n$ for some constant $c<1$ then
$$
\|P_V A P_V\|_\mathrm{op} \asymp \operatorname{trace}[A]/n + \|A\|_\mathrm{op}k/n
$$
up to multiplicative constants dependent ...
- 1,724
1
vote
Additional structures for sparse recovery
Here is my 2cts (this is in no particular order):
L1 analysis -- That's a pretty straightforward thing, but interesting nonetheless
Tree sparse signals (see some work of Bubacarr Bah for instance) ...
- 191
1
vote
Question in Wainwright's paper about signed support recovery in lasso
It seems you are right that there is a gap in the argument.
With this example: $n=p=2$, design $X=I_2$ (identity), support of $\beta^*$ and its complement $S=\{1 \}, S^c=\{2\}$, unknown $\beta^*= (2, ...
- 1,724
Only top scored, non community-wiki answers of a minimum length are eligible