Last Thursday after an email discussion with Thomas Arildsen, I was thinking again to the nice embedding properties discovered by Y. Plan and R. Vershynin in the context of 1-bit compressed sensing (CS) [1].
I was wondering if these could help in showing that a simple variant of basis pursuit denoising using a 
The answer seems to be positive when you merge these results with the simplified BPDN optimality proof of E. Candès [3]. I have gathered these developments in a very short technical report on arXiv:
Laurent Jacques, “On the optimality of a L1/L1 solver for sparse signal recovery from sparsely corrupted compressive measurements” (Submitted on 20 Mar 2013)
Abstract: This short note proves theinstance optimality of a
Briefly, in the context where a sparse or compressible signal 
where 
provides, under certain conditions, a bounded reconstruction error (aka
Noticeably, the two conditions (2) and (3) are not unrealistic, I mean, they are not worst than assuming the common restricted isometry property 
. Indeed, thanks to [1,2], we can show that they hold for random Gaussian matrices as soon as 
As explained in the note, it seems also that the dependency in 
Comments are of course welcome
References:
[1] Y. Plan and R. Vershynin, “Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach,” IEEE Transactions on Information Theory, to appear., 2012.
[2] Y. Plan and R. Vershynin, “Dimension reduction by random hyperplane tessellations,” arXiv preprint arXiv:1111.4452, 2011.
[3] E. Candès, “The restricted isometry property and its implications for compressed sensing,” Compte Rendus de l’Academie des Sciences, Paris, Serie I, vol. 346, pp. 589–592, 2008.
[4] L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk, “Robust 1-Bit Compressive Sensing via Binary Stable Embeddings of Sparse Vectors”
IEEE Transactions on Information Theory, in press.
that does not respect the restricted isometry property (RIP) [1]. I recall that such a matrix is RIP if there exists a (restricted isometry) constant 
such that, for any 
-sparse vector 
,
.
in 
and generate randomly two Gaussian matrices 
and 
in 
with i.i.d. entries drawn from 
. From the vectors 
and 
, you can form two new vectors 
and 
such that 
and 
.
. Then the first column of 
and the rest of the matrix is independent of 
and 
. Conditionally to the value of these two diagonal matrices, this part of 
entry (
) of variance 
. Then, the condition can be removed by expectation rule to lead to the cdf of 
which shows, by construction, that at least one 
, we clearly have 
for any 
. Therefore, we can alway take the norm of 
sufficiently small so that 
is far from 
.
complex values in half the noiselet-frequency domain, and concatenate the real and the imaginary part into a real vector of length 
. The adjoint (transposed) operation — often needed in most of Compressed Sensing solvers — must of course sum the previously split real and imaginary parts into ![[0, 1]](http://s0.wp.com/latex.php?latex=%5B0%2C+1%5D&bg=ffffff&fg=333333&s=0 "[0, 1]")
, is defined thanks to the recursive formulas:
. Their recursive definition is
,
,
, that is, for functions of
and indices 
or 
, is simply a common 
, which are of course complex conjugate of each other.
of a real vector 
of length 
) involving the noiselets of indices 
, the resulting decomposition diagram is fully symmetric (with a complex conjugation) under a flip of indices 
, for 
.
,
the complex conjugation, if 
, that is 
independent real values in total, as obtained by concatenating the real and the imaginary parts (see above).
take the complex values 
, never 
the 
for the Haar wvaelet basis, and it corresponds to slightly higher values for the Daubechies wavelets D4 and D8 respectively (see, e.g., E.J. Candès and M.B. Wakin, 
computations. You start from the approximation coefficients computed at the finest scale, using then the wavelet scaling relations to compute the detail and approximation coefficients at the second scale, and so on. Because of the sub-sampling occuring at each scale, the complexity is proportional to the number of coefficients, that is, it is 
, since the final diagram has 
levels, each involving 
multiplication-additions.
(e.g. 
for some sparse vector 
and a “kind” function 
), I’m wondering if the concentration results above are better than those coming from the classical concentration inequalities (based on the Lipschitz properties of 
As detected by 
on the appropriate interval is given by the dual norm on 
, that part should be fine (for the one norm this gives the infinity norm).
. It is not immediately obvious how to (efficiently) solve the related problem (for a given 
subject to 
.
subject to 
,
(i.e. in the 
norm used on the 
norm of the gradient components) and in particular they answer to the problem of finding and computing the corresponding dual norms. For the usual TV norm, this leads to the G-norm :
is the discrete divergence operator defined as the adjoint of the finite difference gradient operator 
used to defined the TV norm. In other words, 
, where 
and 
.
