The recovery of signals that are sparse not in a given basis, but rather sparse with respect to an over-complete dictionary is one of the most flexible settings in the field of compressed sensing with numerous applications. As in the standard …

We prove new results about the robustness of well-known convex noise-blind optimization formulations for the reconstruction of low-rank matrices from underdetermined linear measurements. Our results are applicable for symmetric rank-one measurements …

We prove new results about the robustness of noise-blind decoders for the problem of re- constructing a sparse vector from underdetermined linear measurements. Our results imply provable robustness of equality-constrained l1-minimization for random …

We study the geometry of centrally-symmetric random polytopes, generated by $N$ independent copies of a random vector $X$ taking values in ${\mathbb{R}^n}$. We show that under minimal assumptions on $X$, for $N \gtrsim n$ and with high probability, …

For a large class of random matrices $A$ with i.i.d. entries we show that the $\ell_1$-quotient property holds with probability exponentially close to $1$. In contrast to previous results, our analysis does not require concentration of the entrywise …