Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [compressed-sensing]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
64 views

When does Basis Pursuit and LASSO give the same answer?

There are 3 different but related optimization questions that one can frame given a $y \in \mathbb{R}^n$ and $A \in \mathbb{R}^{n \times m}$ and constants $\epsilon, \lambda, k > 0$, $$\text{...
0
votes
0answers
35 views

Lowerbound to sample complexity or run-time of doing sparse-coding

I noticed this interesting analogous discussion that happened here, Lower bound proof for compressive sensing (Gel'fand widths)? What is the closest analogue know for such a result for sparse-...
1
vote
0answers
41 views

Stable recovery of signals by $\ell_1$ optimization

Suppose the received vector $y$ is generated from a vector $x^*$ as $y = { D}x^* + z$ for some ``dictionary" matrix ${D}$ and noise vector $z$ s.t for some $\epsilon >0$ we have, $\Vert z \Vert_2 \...
3
votes
0answers
80 views

Complexity of Underdetermined Systems [closed]

Given a field $\mathbb{F}$ and a consistent underdetermined system $Ax=b$ over $\mathbb{F},$ $A\in \mathbb{F}^{m \times N}$ and $b \in \mathbb{F}^m,$ finding a vector $z \in \mathbb{F}^N$ such that $...
3
votes
1answer
232 views

The connection between compressed sensing and sparse representation

If I understand correctly, Compressed Sensing as an application of Sparse Representation is defined as: To find linear ...
3
votes
0answers
63 views

Estimate smooth vector, from dot-product queries

I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
5
votes
2answers
385 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
99 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
80 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 frequency....
0
votes
0answers
335 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
1k 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
0answers
346 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
307 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?
22
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 ...