<p>In the paper [A], the following linear algebra result (Lemma 5 in [A])  is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.  </p>

<p>Lemma: Let $1 \le s \le n$. There is a choice $k = O(s)$ and a random linear function $L : \mathbb{R}^n \rightarrow \mathbb{R}^k$ (generated from $O(k\log n)$ random bits), and a recovery procedure that on input $L(x)$ outputs $x' \in \mathbb{R}^n$ or $DENSE$ such that, for any $s$-sparse vector $x$, the output is $x'=x$ with probability $1$ and, for any non-$s$-sparse vector $x$, the output is $DENSE$ with high probability. </p>

<p>Is there a reference for this result or an easy argument why this is true? </p>

<p>[A] Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems.
Hossein Jowhari, Mert Sağlam, Gábor Tardos
<a href="http://arxiv.org/abs/1012.4889">arXiv</a></p>

CC BY-SA 3.0
2015-01-16T19:35:51.803Z
I am genuinely puzzled by this claim. For one thing, if any $s$-sparse $x$ is recovered with probability $1$, then there exists a fixed matrix $L$ which allows recovering any rational $s$-sparse vector exactly with $O(s)$ measurements (because the set of rational $s$-sparse vectors is countable, so you can take a union bound). I don't think this is known. What am I missing?
Sasho Nikolov
CC BY-SA 3.0
2015-01-16T21:53:37.013Z
I do know how to recover an $s$-sparse vector with $1 - 1/s^c$ probability and $O(s\log s)$ measurements if you are interested.
Sasho Nikolov
CC BY-SA 3.0
2015-01-17T11:53:01.183Z
@SashoNikolov: Yes that would be interesting too.
more_question
CC BY-SA 3.0
2016-03-01T18:18:27.520Z
@SashoNikolov Could you provide some more info about your claim?
dtldarek
<reference-request><linear-algebra><randomness><streaming-algorithms>
Reconstruction of sparse vectors from random matrices
more_question
# Reconstruction of sparse vectors from random matrices

(Asked by: username_0 on 2015-01-16)

In the paper [A], the following linear algebra result (Lemma 5 in [A]) is stated as being well known. Note that a vector is $s$-sparse if it contains at most $s$ non-zero entries.

Lemma: Let $1 \le s \le n$. There is a choice $k = O(s)$ and a random linear function $L : \mathbb{R}^n \rightarrow \mathbb{R}^k$ (generated from $O(k\log n)$ random bits), and a recovery procedure that on input $L(x)$ outputs $x' \in \mathbb{R}^n$ or $DENSE$ such that, for any $s$-sparse vector $x$, the output is $x'=x$ with probability $1$ and, for any non-$s$-sparse vector $x$, the output is $DENSE$ with high probability.

Is there a reference for this result or an easy argument why this is true?

[A] Tight Bounds for Lp Samplers, Finding Duplicates in Streams, and Related Problems.
Hossein Jowhari, Mert Sağlam, Gábor Tardos
[arXiv](http://arxiv.org/abs/1012.4889)

**Tags:** reference-request, linear-algebra, randomness, streaming-algorithms

> **Comments:**
> **username_1**: I am genuinely puzzled by this claim. For one thing, if any $s$-sparse $x$ is recovered with probability $1$, then there exists a fixed matrix $L$ which allows recovering any rational $s$-sparse vector exactly with $O(s)$ measurements (because the set of rational $s$-sparse vectors is countable, so you can take a union bound). I don't think this is known. What am I missing?  
> **username_1**: I do know how to recover an $s$-sparse vector with $1 - 1/s^c$ probability and $O(s\log s)$ measurements if you are interested.  
> **username_0**: @SashoNikolov: Yes that would be interesting too.  
> **username_2**: @SashoNikolov Could you provide some more info about your claim?  

---

## 0 answers

