5
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 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$
    – Sasho Nikolov
    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$
    – Sasho Nikolov
    Jan 16, 2015 at 21:53
  • $\begingroup$ @SashoNikolov: Yes that would be interesting too. $\endgroup$
    – more_question
    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

0

Reset to default

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.