The compressed-sensing tag has no wiki summary.
-3
votes
1answer
75 views
Proof of non-existence of the universal archiver? [closed]
Does anybody knows a proof that no algorithm $A$ exists that can reversibly transform every possible finite sequence $S$ to the sequence $C$ of smaller size?
Here I assume $S$ and $C$ to be a finite ...
3
votes
0answers
69 views
Efficiently Detecting “edges” in the time frequency plane
Given a signal $y(t)\in\mathbb{R}$ I wish to detect edge patterns. $s(f,t)$ is a time-frequency decomposition of $y(t)$ in some window $(t-n,t+n)$ so that $f$ loosely corresponds to a local ...
0
votes
0answers
114 views
norms of compressible and incompressible vector
Let $a$ be a vector in $R^m$, such that $\sum_{i=1}^ma_i=0$
I would like to bound $\sqrt{2m(2m-1)}\|a\|_{\infty}$ by $\sqrt{2m}\|a\|_2$ (or other way arround with the sharp constants), in the case ...
9
votes
0answers
303 views
Complexity of finding the leading eigenvector of a graph Laplacian
Let ${\bf L}$ be the $n\times n$ Laplacian of a graph. What is the worst case complexity for calculating the maximum eigeinvector of ${\bf L}$?
Are there any families of Laplacians for which it takes ...
17
votes
1answer
296 views
complexity of checking if a subspace is a Euclidean section of L1
If $X$ is a linear subspace of ${\mathbb R}^n$, $X$ is high-dimensional, and for every $x\in X$ we have
$(1-\epsilon) \sqrt n ||x||_2 \leq ||x||_1 \leq \sqrt n ||x||_2$
for some small $\epsilon ...
1
vote
2answers
264 views
Complexity of Smoothed $\ell_0$ algorithm
I wanted to compute the complexity of a smoothed $\ell_0$ algorithm in BigO notation. The algorithm can be found here. Can anybody help me in this regard?
18
votes
6answers
1k views
Analogs of compressed sensing
In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from ...
