CS: Convex iteration method, Statistical Estimation in High Dimension,, Super-resolution far-field ghost imaging via compressive sampling

Happy Thanksgiving y'all.


First, I hope you are not shell shocked from yesterday's post on the Approximate Message Passing Algorithm. Second, Jon Dattorro sent me the following:

I have published a derivation of direction vector for the convex iteration method of cardinality minimization (compressed sensing) here (p.322):

http://meboo.convexoptimization.com/Meboo.html

Specifically: The direction vector has been interpreted in the past, by others, as "yet another weighting" for the compressed sensing problem. The derivation I provide proves that the optimal direction vector is a binary vector complementary to the optimal solution; i.e., the binary values {0,1} of the direction vector are not at all arbitrary, but now have firm theoretical foundation.

Existence of such an optimal direction vector is assured under the assumption that a cardinality-k solution to the compressed sensing problem exists. But finding that direction vector remains a hard problem.

When a direction vector is 1, then convex iteration is equivalent to the conventional compressed sensing problem. But I show, by numerous example, that there are far better directions than 1 that produce significantly better results than compressed sensing alone.

Thanks Jon!

I just started a Google Wave with the provocative title entitled "Compressive Sensing / Compressed Sensing : What is it good for ?", I hope you'll join!

Today I finally met Andrew Gelman who's popular blog is listed on the right hand side of this blog. He was giving a talk at AppliBUGS (the talk is now here). He made an interesting presentation where he talked about building supergraphs of models where each node would be a statistical model and every node (model) would only differ from one another by one feature.


I am going to have to think how some of the machine learning techniques on manifold could be applied to this new meta-formalism.

I met Andrew, but I am afraid I won't meet Buzz Aldrin, too bad, oh well one famous person a day is good enough in my book :-)


Karim Lounici's Ph.D. thesis is out. The summary reads: Statistical Estimation in High Dimension, Sparsity and Oracle Inequalities

We treat two subjects. The first subject is about statistical learning in high-dimension, that is when the number of paramaters to estimate is larger than the sample size. In this context, the generally adopted assumption is that the number of true parameters is much smaller than the number of potential paramaters. This assumption is called the ``\emph{sparsity assumption}''. We study the statistical properties of two types of procedures: the penalized risk minimization procedures with a $l_{1}$ penalty term on the set of potential parameters and the exponential weights procedures. The second subject is about the study of two aggregation procedures in a density estimation problem. We establish oracle inequalities for the $L^{\pi}$ norm, $1\leqslant \pi \leqslant \infty$. Next, we exploit these results to build minimax rate adaptive estimators of the density.

From Arxiv, we finally have the fascinating: Super-resolution far-field ghost imaging via compressive sampling by Wenlin Gong, Shensheng Han. The abstract reads:

For classical source, the uncertainty relation involving the product of conditional variances in position and momentum limits the imaging resolution of optical system. Based on ghost imaging (GI) and compressive sampling (CS) theory, an imaging approach called ghost imaging via compressive sampling (GICS) with thermal light is reported. For the first time, a super-resolution image with high quality is obtained in the far field by GICS reconstruction. Physical principle of GICS and the resolution limit of conventional imaging, GI and GICS are also discussed.

In a different direction, if the Earth had rings, this is what they'd look like from the ground. Breathtaking.



Credit: NASA, Roy Prol.