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

  • 2
    $\begingroup$ 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? $\endgroup$ Jan 16, 2015 at 19:35
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 16, 2015 at 21:53
  • $\begingroup$ @SashoNikolov: Yes that would be interesting too. $\endgroup$ Jan 17, 2015 at 11:53
  • 1
    $\begingroup$ @SashoNikolov Could you provide some more info about your claim? $\endgroup$
    – dtldarek
    Mar 1, 2016 at 18:18


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.