Let $A \in \mathbb{R}^{m \times n}$.


Is it true that $$\min \limits\_{Q \in \mathbb{R}^{n \times m}}|I - QA|\_{\infty} < \frac{1}{2}$$ is criteria for the uniqueness of the 1-sparse solution to 


$\min \limits\_{x \text{ s.t.} Ax=y} |x|\_1$ for any $y$.


If yes, where can I read about this result. I am not 100% sure that I have got the criteria correctly.


Update. $|M|\_{\infty} = \max \limits\_{i,j} |M\_{ij}|$



Uniqueness of l1 minimization
Yes, this is true. Since there exists a 'decoder' $Q$ which gives a value on the right hand side (close to or equal to) $\frac{1}{2}$, the pair $(A,Q)$ are $(\ell\_\infty, \ell\_1)$-instance optimal (see [this talk](http://math.univ-lille1.fr/~cempi/activites_scientifiques/FR/conf/files/Lecon3B.pdf) of Foucart, pg 75, for details). From this it follows that no non-trivial $2$-sparse vectors lie in the kernel of $A$ and that $A$ satisfies the null space property of order $2$ for recovery via $\ell\_1$-minimization.


Chapter 11 of Foucart's [book](https://link-springer-com.prx.library.gatech.edu/book/10.1007%2F978-0-8176-4948-7) is another reference for this topic.


