min

Herein we show that a positive encoder gap exists for signals that are (approximately)k-sparse. Furthermore, considerZ0 as the set of m random variablesz that only differs fromZ in itsith variable, z0i = (y0i,x0i). We finally get expressions for the covering number as a function of . Thus,weneedλ/m 2λ/(1+ν)2, which is satisfied as long asm 2 (1+ν)2/2, which is satisfied in all relevant scenarios. For remarkc), denote x = x0 +v, and note that the minimizer of the above optimization problem satisfies (as follows from optimality of the minimizer [Mehta and Gray,2013, Lemma 13 of Supplementary]) 1 2 kx DϕD(x)k22+λkϕD(x)k1= 1 2 kxk22 1 2 kDϕD(x)k22.