CS: Sparse approx, Body Area Networks, Johnson-Lindenstrauss Transform, Superselectors, stochastic search method for dimensionality reduction in classification, Adaptive estimation of covariance matrices via Cholesky decomposition

Today, we have some blog entries, three papers and two articles in the blogosphere/press related to compressive sensing, without further due, here they are:

From the blogs:
Bob

• Greedy Decomposition of Stationary Signals
• Un Homme et Une Femme: Audio Fingerprinting and Matching in MATLAB
• Paper of the Day (Po'D): Recursive Nearest Neighbor Search in a Sparse Domain Applied to Comparing Audio Signals Edition
• Comparing Audio Signals in a Sparse Domain
• A Successful HAID 2010!

Gonzalo:

• Spectral Sensing at CIP 2010
• Final FCC rules for the unlicensed use of the TV white spaces today?
• FCC "final" rules. Cognitive radio or just unlicensed access?
• ECC Report 159: European white space devices

In the press:

• Michael Elad Talks About the field of Sparse Approximation (Michael Elad has also written a book on Sparse and Redundant Representations: From Theory to Applications in Signal and Image Processing)
• Qualcomm's ultralow power tech targets body area networks

From Suresh:

The Johnson-Lindenstrauss Transform: An Empirical Study (pdf is here) by Suresh Venkatasubramanian and Qiushi Wang. The abstract reads:

The Johnson-Lindenstrauss Lemma states that a set of $n$ points may be embedded in a space of dimension $O(\log n/\eps^2)$ while preserving all pairwise distances within a factor of $(1+\epsilon)$ with high probability. It has inspired a number of proofs that extend the result, simplify it, and improve the efficiency of computing the resulting embedding. The lemma is a critical tool in the realm of dimensionality reduction and high dimensional approximate computational geometry. It is also employed for data mining in domains that analyze intrinsically high dimensional objects such as images and text. However, while algorithms for performing the dimensionality reduction have become increasingly sophisticated, there is little understanding of the behavior of these embeddings in practice. In this paper, we present the first comprehensive study of the empirical behavior of algorithms for dimensionality reduction based on the JL Lemma.

Our study answers a number of important questions about the quality of the embeddings and the performance of algorithms used to compute them. Among our key results:

• Determining a likely range for the big-Oh constant in practice for the dimension of the target space, and demonstrating the accuracy of the predicted bounds.
• Finding `best in class’ algorithms over wide ranges of data size and source dimensionality, and showing that these depend heavily on parameters of the data as well its sparsity.
• Developing the best implementation for each method, making use of non-standard optimized codes for key subroutines.
• Identifying critical computational bottlenecks that can spur further theoretical study of efficient algorithms.

From arxiv:

Superselectors: Efficient Constructions and Applications by Ferdinando Cicalese, Ugo Vaccaro. The abstract reads:

We introduce a new combinatorial structure: the superselector. We show that superselectors subsume several important combinatorial structures used in the past few years to solve problems in group testing, compressed sensing, multi-channel conflict resolution and data security. We prove close upper and lower bounds on the size of superselectors and we provide efficient algorithms for their constructions. Albeit our bounds are very general, when they are instantiated on the combinatorial structures that are particular cases of superselectors (e.g., (p,k,n)-selectors, (d,\ell)-list-disjunct matrices, MUT_k(r)-families, FUT(k, a)-families, etc.) they match the best known bounds in terms of size of the structures (the relevant parameter in the applications). For appropriate values of parameters, our results also provide the first efficient deterministic algorithms for the construction of such structures.

A multivariate adaptive stochastic search method for dimensionality reduction in classification by Tian Siva Tian, Gareth M. James, Rand R. Wilcox. The abstract reads:

High-dimensional classification has become an increasingly important problem. In this paper we propose a "Multivariate Adaptive Stochastic Search" (MASS) approach which first reduces the dimension of the data space and then applies a standard classification method to the reduced space. One key advantage of MASS is that it automatically adjusts to mimic variable selection type methods, such as the Lasso, variable combination methods, such as PCA, or methods that combine these two approaches. The adaptivity of MASS allows it to perform well in situations where pure variable selection or variable combination methods fail. Another major advantage of our approach is that MASS can accurately project the data into very low-dimensional non-linear, as well as linear, spaces. MASS uses a stochastic search algorithm to select a handful of optimal projection directions from a large number of random directions in each iteration. We provide some theoretical justification for MASS and demonstrate its strengths on an extensive range of simulation studies and real world data sets by comparing it to many classical and modern classification methods.

Adaptive estimation of covariance matrices via Cholesky decomposition by Nicolas Verzelen. The abstract reads:

This paper studies the estimation of a large covariance matrix. We introduce a novel procedure called ChoSelect based on the Cholesky factor of the inverse covariance. This method uses a dimension reduction strategy by selecting the pattern of zero of the Cholesky factor. Alternatively, ChoSelect can be interpreted as a graph estimation procedure for directed Gaussian graphical models. Our approach is particularly relevant when the variables under study have a natural ordering (e.g. time series) or more generally when the Cholesky factor is approximately sparse. ChoSelect achieves non-asymptotic oracle inequalities with respect to the Kullback-Leibler entropy. Moreover, it satisfies various adaptive properties from a minimax point of view. We also introduce and study a two-stage procedure that combines ChoSelect with the Lasso. This last method enables the practitioner to choose his own trade-off between statistical efficiency and computational complexity. Moreover, it is consistent under weaker assumptions than the Lasso. The practical performances of the different procedures are assessed on numerical examples.

Image Credit: NASA/JPL/Space Science Institute, N00164032.jpg was taken on October 06, 2010 and received on Earth October 07, 2010. The camera was pointing toward ATLAS, and the image was taken using the CL1 and CL2 filters.