CS: This week's long post.

The Arxiv experimental search is broken and this is a problem for those of us interested in cross-cutting fields such as compressive sensing. Case in point, there is currently no way to find out if a certain paper has been mentioned in later preprints. In my case, the papers in question are the ones about opaque lenses by Ivo Vellekoop et al such as Measuring the Transmission Matrix in Optics : An Approach to the Study and Control of Light Propagation in Disordered Media by Sebastien Popoff, Goeffroy Lerosey, Remi Carminati, Mathias Fink, A. Claude Boccara, Sylvain Gigan. The abstract reads:

We introduce a method to experimentally measure the monochromatic transmission matrix of a complex medium in optics. This method is based on a spatial phase modulator together with a full-field interferometric measurement on a camera. We determine the transmission matrix of a thick random scattering sample. We show that this matrix exhibits statistical properties in good agreement with random matrix theory and allows light focusing and imaging through the random medium. This method might give important insights into the mesoscopic properties of complex medium.

I'll come back to this paper later. One of the author Mathias Fink, has some interesting views on disordered media.

I am sure that not relying on random matrix theory and svd regularization but on compressive sensing and l1/l0 regularization might prove worth it. In a different direction, I was intringued by these Random Lasers.

The following popped up on the interwebs:

Closed-Form Reconstruction of Sparse Signals from Limited Numbers of Irregular Frequencies by Andrew Yagle. The abstract reads:

The goal is to reconstruct a sparse signal or image from some, but not all, of its discrete Fourier transform (DFT) values. We derive a condition that ensures the sparse solution can be computed in closed form by thresholding the inverse DFT of the known DFT values, with unknown DFT values set to zero.

Hosein Mohimani just let me know that there is a new paper on SL0 entitled: Sparse Recovery using Smoothed $\ell^0$ (SL0): Convergence Analysis by Hosein Mohimani, Massoud Babaie-Zadeh, Irina Gorodnitsky, Christian Jutten. The abstract reads:

Finding the sparse solution of an underdetermined system of linear equations has many applications, especially, it is used in Compressed Sensing (CS), Sparse Component Analysis (SCA), and sparse decomposition of signals on overcomplete dictionaries. We have recently proposed a fast algorithm, called Smoothed $\ell^0$ (SL0), for this task. Contrary to many other sparse recovery algorithms, SL0 is not based on minimizing the $\ell^1$ norm, but it tries to directly minimize the $\ell^0$ norm of the solution. The basic idea of SL0 is optimizing a sequence of certain (continuous) cost functions approximating the $\ell^0$ norm of a vector. However, in previous papers, we did not provide a complete convergence proof for SL0. In this paper, we study the convergence properties of SL0, and show that under a certain sparsity constraint in terms of Asymmetric Restricted Isometry Property (ARIP), and with a certain choice of parameters, the convergence of SL0 to the sparsest solution is guaranteed. Moreover, we study the complexity of SL0, and we show that whenever the dimension of the dictionary grows, the complexity of SL0 increases with the same order as Matching Pursuit (MP), which is one of the fastest existing sparse recovery methods, while contrary to MP, its convergence to the sparsest solution is guaranteed under certain conditions which are satisfied through the choice of parameters.

The SL0 algorithm can be found here.

Also found on Arxiv, Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach by Shashi Kiran Chilappagari, Michael Chertkov, Bane Vasic. The abstract reads:

We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated $512\times120$ matrix. For this example the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.

Some new items from the Rice repository:

Sparse Sensing DNA Microarray-Based Biosensor: Is It Feasible? by Mojdeh Mohtashemi. The asbtract reads:

Conventional microarray-based biosensors can only detect a limited number of organisms, and adding sensor capabilities requires re-engineering of reagents and devices to detect the presence of a novel microbial organism. To overcome these limitations, the size of the microarray may need to be prohibitively large, an impractical proposition, cost-wise, using current technology. We hypothesized that a relatively small number of oligomers is sufficient to design a microarray capable of differentiating between the genomic signatures of multiple organisms. To test this hypothesis, we designed a sparse, pseudorandom prototype microarray-based biosensor by generating 12,600 25bp oligomer probes derived from a mathematical model based on random selection of DNA sequences from seven pathogenic prokaryotic genomes. To enable identification of novel organisms, a reference library of pure genomic DNA was generated from three simulant organisms that are known to be phylogenetically distant from the seven base species used to generate the probes. These simulants were combined to produce complex DNA samples meant to mimic the uncertainty and complexity of an unknown environmental genomic background. A mathematical model was then developed to capture the signature of each simulant organism. The model detected the presence of all three simulant organisms in the mixed DNA samples with high accuracy.

Compressed Least-Squares Regression by Odalric-Ambrym Maillard, Rémi Munos. The abstract reads:

We consider the problem of learning, from K data, a regression function in a linear space of high dimension N using projections onto a random subspace of lower dimension M. From any algorithm minimizing the (possibly penalized) empirical risk, we provide bounds on the excess risk of the estimate computed in the projected subspace (compressed domain) in terms of the excess risk of the estimate built in the high-dimensional space (initial domain). We show that solving the problem in the compressed domain instead of the initial domain reduces the estimation error at the price of an increased (but controlled) approximation error. We apply the analysis to Least-Squares (LS) regression and discuss the excess risk and numerical complexity of the resulting ``Compressed Least Squares Regression'' (CLSR) in terms of N, K, and M. When we choose M=O(\sqrt{K}), we show that CLSR has an estimation error of order O(\log K / \sqrt{K}).

Beyond alias hierarchical scale curvelet interpolation of regularly and irregularly sampled seismic data by Mostafa Naghizadeh and Mauricio D. Sacchi. The abstract reads:

We propose a robust interpolation scheme for aliased regularly sampled seismic data that uses the curvelet transform. In a first pass, the curvelet transform is used to compute the curvelet coefficients of the aliased seismic data. The aforementioned coefficients are divided into two groups of scales: alias-free and alias-contaminated scales. The alias-free curvelet coefficients are upscaled to estimate a mask function that is used to constrain the inversion of the alias-contaminated scale coefficients. The mask function is incorporated into the inversion via a minimum norm least squares algorithm that determines the curvelet coefficients of the desired alias free data. Once the aliasfree coefficients are determined, the curvelet synthesis operator is used to reconstruct seismograms at new spatial positions. The proposed method can be used to reconstruct both regularly and irregularly sampled seismic data. We believe that our exposition leads to a clear unifying thread between f-x Spitz (1991) and f-k Gulunay (2003) beyond-alias interpolation methods and curvelet reconstruction. Likewise in f-x and f-k interpolation, we stress the necessity of examining seismic data at different scales (frequency bands) in order to come up with viable and robust interpolation schemes. Synthetic and real data examples are used to illustrate the performance of the proposed curvelet interpolation method.