Sunday, November 07, 2010

CS; Performance Analysis of Spectral Clustering on Compressed, Incomplete and Inaccurate Measurements, A Signal-agnostic Compressed Sensing Acquisition System for Wireless and Implantable Sensors, The Lasso under Heteroscedasticity, CS-Orion

We have three papers today, one of which (the last one) chose a title that sounds a little different:
Spectral clustering is one of the most widely used techniques for extracting the underlying global structure of a data set. Compressed sensing and matrix completion have emerged as prevailing methods for efficiently recovering sparse and partially observed signals respectively. We combine the distance preserving measurements of compressed sensing and matrix completion with the power of robust spectral clustering. Our analysis provides rigorous bounds on how small errors in the affinity matrix can affect the spectral coordinates and clusterability. This work generalizes the current perturbation results of two-class spectral clustering to incorporate multi-class clustering with k eigenvectors. We thoroughly track how small perturbation from using compressed sensing and matrix completion affect the affinity matrix and in succession the spectral coordinates. These perturbation results for multi-class clustering require an eigengap between the kth and (k+1)th eigenvalues of the affinity matrix, which naturally occurs in data with k well-defined clusters. Our theoretical guarantees are complemented with numerical results along with a number of examples of the unsupervised organization and clustering of image data.

A signal-agnostic compressed sensing (CS) acquisition system is presented that addresses both the energy and telemetry bandwidth constraints of wireless sensors. The CS system enables continuous data acquisition and compression that are suitable for a variety of biophysical signals. A hardware efficient realization of the CS sampling demonstrates data compression up to 40x on an EEG signal while maintaining low perceptual loss in the reconstructed signal. The proposed system also simultaneously relaxes the noise and resolution constraints of the analog front end (AFE) and ADC by nearly an order of magnitude. The CS sampling hardware is implemented in a 90 nm CMOS process and consumes 1.9 μW at 0.6 V and 20 kS/s.

The Lasso under Heteroscedasticity by Jinzhu Jia, Karl Rohe, Bin Yu. The abstract reads:
The performance of the Lasso is well understood under the assumptions of the standard linear model with homoscedastic noise. However, in several applications, the standard model does not describe the important features of the data. This paper examines how the Lasso performs on a non-standard model that is motivated by medical imaging applications. In these applications, the variance of the noise scales linearly with the expectation of the observation. Like all heteroscedastic models, the noise terms in this Poisson-like model are \textit{not} independent of the design matrix.
More specifically, this paper studies the sign consistency of the Lasso under a sparse Poisson-like model. In addition to studying sufficient conditions for the sign consistency of the Lasso estimate, this paper also gives necessary conditions for sign consistency. Both sets of conditions are comparable to results for the homoscedastic model, showing that when a measure of the signal to noise ratio is large, the Lasso performs well on both Poisson-like data and homoscedastic data.
Simulations reveal that the Lasso performs equally well in terms of model selection performance on both Poisson-like data and homoscedastic data (with properly scaled noise variance), across a range of parameterizations. Taken as a whole, these results suggest that the Lasso is robust to the Poisson-like heteroscedastic noise.
Finally, there is a group funded by the EU that seems to focus on Compressed Sensing for Remote Imaging in Aerial and Terrestrial Surveillance. It is called CS-Orion.

Credit: NASA/JPL-Caltech/UMD, Epoxi, close encounter to Hartley 2

No comments: