The compressed-sensing tag has no wiki summary.
0
votes
0answers
83 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 ...
0
votes
0answers
69 views
The notion of approximately sparse vectors in compressed sensing
An x in $\mathbb{R}^n$ is said to be sparse if many of it's coefficients are zeroes. x is said to be compressible(approximately sparse) if many of its coefficients are close to zero.This is how it is ...
9
votes
0answers
198 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
273 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
250 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?
17
votes
7answers
996 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 ...
