Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
2answers
75 views

Lower bound proof for compressive sensing (Gel'fand widths)?

Let $x \in \mathbb{R}^n$ have $k$ non-zero entries. The main insight of compressive sensing is that there exist $m\times n$ matrices $A$ with $m = O(k \log n/k)$ such that any $x$ can be recovered ...
-3
votes
1answer
96 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
76 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
161 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 ...
11
votes
0answers
434 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
314 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
274 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 ...