CS: the Kernel Trick in Compressive Sensing, Online Group-Structured Dictionary Learning, Matrix Completion, Reconstruction of Binary Functions and Shapes from Incomplete Frequency Information, Compressive Sensing for Streaming Signals, Algorithm-Enabled Low-Dose Micro-CT Imaging, Sparse OCT

Gabriel Peyre sent me the following:

I have set up a Numerical Tour on matrix completion
http://www.ceremade.dauphine.fr/~peyre/numerical-tour/tours/cs_4_matrix_completion/This can be useful teaching material for readers of nuit blanche.

Thanks Gabriel.

Zoltan Szabo let me know of his upcoming CVPR paper below, but he also let me know that his code would be forthcoming. Stay tuned. Online Group-Structured Dictionary Learning (OSDL) by Zoltan Szabo, Barnabas Poczos and Andras Lorincz. The abstract reads:

We develop a dictionary learning method which is (i) online, (ii) enables overlapping group structures with (iii) non-convex sparsity-inducing regularization and (iv) handles the partially observable case. Structured sparsity and the related group norms have recently gained widespread attention in group-sparsity regularized problems in the case when the dictionary is assumed to be known and fixed. However, when the dictionary also needs to be learned, the problem is much more difficult. Only a few methods have been proposed to solve this problem, and they can handle two of these four desirable properties at most. To the best of our knowledge, our proposed method is the first one that possesses all of these properties. We investigate several interesting special cases of our framework, such as the online, structured, sparse non-negative matrix factorization, and demonstrate the efficiency of our algorithm with several numerical experiments.

Deanna Needell has made available two of her recent presentations: Compressed sensing and redundancy and Acceleration of Randomized Kaczmarz via the JL Lemma

Here what I found on the interwebs:

Using the Kernel Trick in Compressive Sensing: Accurate Signal Recovery from Fewer Measurements by Hanchao Qi, Shannon Hughes. The abstract reads:

Compressive sensing accurately reconstructs a signal that is sparse in some basis from measurements, generally consisting of the signal’s inner products with Gaussian random vectors. The number of measurements needed is based on the sparsity of the signal, allowing for signal recovery from far fewer measurements than is required by the traditional Shannon sampling theorem. In this paper, we show how to apply the kernel trick, popular in machine learning, to adapt compressive sensing to a different type of sparsity. We consider a signal to be “nonlinearly K-sparse” if the signal can be recovered as a nonlinear function of K underlying parameters. Images that lie along a low-dimensional manifold are good examples of this type of nonlinear sparsity. It has been shown that natural images are as well [1]. We show how to accurately recover these nonlinearly K-sparse signals from approximately 2K measurements, which is often far lower than the number of measurements usually required under the assumption of sparsity in an orthonormal basis (e.g. wavelets). In experimental results, we find that we can recover images far better for small numbers of compressive sensing measurements, sometimes reducing the mean square error (MSE) of the recovered image by an order of magnitude or more. A bound on the error of our recovered signal is also proved.

Reconstruction of Binary Functions and Shapes from Incomplete Frequency Information by Yu Mao. The abstract reads:

The characterization of a binary function by partial frequency information is considered. We show that it is possible to reconstruct the binary signal from incomplete frequency measurements via solving a simple linear optimization problem. We further prove that if the binary function is spatially structured, e.g. a general black-write image or an indicator function of a shape, then it can be recovered from very few low frequency measurements in general. These results would lead to efficient methods of sensing, characterizing and recovering a binary signal or a shape as well as other applications like deconvolution of binary function from low-pass filter. Numerical results are demonstrated to validate the theoretical arguments.

Compressive Sensing for Streaming Signals using the Streaming Greedy Pursuit by Petros Boufounos and Salman Asif. The abstract reads:

Compressive Sensing (CS) has recently emerged as significant signal processing framework to acquire and reconstruct sparse signals at rates significantly below the Nyquist rate. However, most of the CS development to-date has focused on finite-length signals and representations. In this paper we present a new CS framework and a greedy reconstruction algorithm, the Streaming Greedy Pursuit (SGP), explicitly designed for streaming applications and signals of unknown length. Our sampling framework is designed to be causal and implementable using existing hardware architectures. Furthermore, our reconstruction algorithm provides explicit computational guarantees, which makes it appropriate for real-time system implementations. Our experimental results on very long signals demonstrate the good performance of the SGP and validate our approach.

Algorithm-Enabled Low-Dose Micro-CT Imaging by Xiao Han, Junguo Bian, Diane R. Eaker, Timothy L. Kline, Emil Y. Sidky, Erik L. Ritman, and Xiaochuan Pan. The abstract reads:

Micro-computed tomography (micro-CT) is an important tool in biomedical research and preclinical applications that can provide visual inspection of and quantitative information about imaged small animals and biological samples such as vasculature specimens. Currently, micro-CT imaging uses projection data acquired at a large number (300–1000) of views, which can limit system throughput and potentially degrade image quality due to radiation-induced deformation or damage to the small animal or specimen. In this work, we have investigated low-dose micro-CT and its application to specimen imaging from substantially reduced projection data by using a recently developed algorithm, referred to as the adaptive-steepest-descent-projection-onto-convex-sets (ASD-POCS) algorithm, which reconstructs an image through minimizing the image total-variation and enforcing data constraints. To validate and evaluate the performance of the ASD-POCS algorithm, we carried out quantitative evaluation studies in a number of tasks of practical interest in imaging of specimens of real animal organs. The results show that the ASD-POCS algorithm can yield images with quality comparable to that obtained with existing algorithms, while using one-sixth to one quarter of the 361-view data currently used in typical micro-CT specimen imaging.

Sparse OCT: optimizing compressed sensing in spectral domain optical coherence tomography by Xuan Liu and Jin U. Kang. The abstract reads:

We applied compressed sensing (CS) to spectral domain optical coherence tomography (SD-OCT). Namely, CS was applied to the spectral data in reconstructing A-mode images. This would eliminate the need for a large amount of spectral data for image reconstruction and processing. We tested the CS method by randomly undersampling k-space SD-OCT signal. OCT images are reconstructed by solving an optimization problem that minimizes the l1 norm to enforce sparsity, subject to data consistency constraints. Variable density random sampling and uniform density random sampling were studied and compared, which shows the former undersampling scheme can achieve accurate signal recovery using less data.

Image Credit: NASA/JPL/Space Science Institute
N00171120.jpg was taken on April 06, 2011 and received on Earth April 08, 2011. The camera was pointing toward TITAN at approximately 2,044,867 kilometers away, and the image was taken using the CL1 and MT2 filters.