CS: Manifold Models for Signals and Images, Thresholded Basis Pursuit, Maximum Entropy Method in CS Reconstruction and DARPA mathematical challenges.

We have three papers today related to different reconstruction techniques.

The first one refers back to the manifold signal processing we have seen before being developed by Michael Wakin in his thesis. While there is an issue of non-differentiability in images featuring occluding elements, the smooth manifold approach is somehow ideally fitted with that of textures. The paper by Gabriel Peyre entitled Manifold Models for Signals and Images looks at this problem. The abstract reads:

This article proposes a new class of models for natural signals and images. The set of patches extracted from the data to analyze is constrained to be close to a low dimensional manifold. This manifold structure is detailed for various ensembles suitable for natural signals, images and textures modeling. These manifolds provide a low-dimensional parametrization of the local geometry of these datasets. These manifold models can be used to regularize inverse problems in signal and image processing. The restored signal is represented as a smooth curve or surface traced on the manifold that matches the forward measurements. A manifold pursuit algorithm computes iteratively a solution of the manifold regularization problem. Numerical simulations on inpainting and compressive sensing inversion show that manifolds models bring an improvement for the recovery of data with geometrical features.

I note the development of a manifold based greedy algorithm called manifold pursuit.




The second paper is Thresholded Basis Pursuit: Quantizing Linear Programming Solutions for Optimal Support Recovery and Approximation in Compressed Sensing by Venkatesh Saligrama, Manqi Zhao. The abstract reads:

We consider the classical Compressed Sensing problem. We have a large under-determined set of noisy measurements Y=GX+N, where X is a sparse signal and G is drawn from a random ensemble. In this paper we focus on a quantized linear programming solution for support recovery. Our solution of the problem amounts to solving $\min \|Z\|_1 ~ s.t. ~ Y=G Z$, and quantizing/thresholding the resulting solution $Z$. We show that this scheme is guaranteed to perfectly reconstruct a discrete signal or control the element-wise reconstruction error for a continuous signal for specific values of sparsity. We show that in the linear regime when the sparsity, $k$, increases linearly with signal dimension, $n$, the sign pattern of $X$ can be recovered with $SNR=O(\log n)$ and $m= O(k)$ measurements. Our proof technique is based on perturbation of the noiseless $\ell_1$ problem. Consequently, the achievable sparsity level in the noisy problem is comparable to that of the noiseless problem. Our result offers a sharp characterization in that neither the $SNR$ nor the sparsity ratio can be significantly improved. In contrast previous results based on LASSO and MAX-Correlation techniques assume significantly larger $SNR$ or sub-linear sparsity. We also show that our final result can be obtained from Dvoretsky theorem rather than the restricted isometry property (RIP). The advantage of this line of reasoning is that Dvoretsky's theorem continues to hold for non-singular transformations while RIP property may not be satisfied for the latter case.

I note the independence of their approach from the Restricted Isometry Property.

Finally, the third paper is about using a maximum entropy method in A New Reconstruction Approach to Compressed Sensing by Tianjing Wang and Zhen Yang. The abstract reads:

Compressed sensing is a new concept in signal processing where one seeks to minimize the number of measurements to be taken from signals while still retaining the information necessary to approximate them well. Nonlinear algorithms, such as norm optimization problem, are used to reconstruct the signal from the measured data. This paper proposes a maximum entropy function method which intimately relates to homotopy method as a computational approach to solve the optimization problem. Maximum entropy function method makes it possible to design random measurements which contain the information necessary to reconstruct signal with accuracy. Both the theoretical evidences and the extensive experiments show that it is an effective technique for signal reconstruction. This approach offers several advantages over other methods, including scalability and robustness.

Finally, DARPA has put out a research request for proposals entitled Mathematical Challenges. Compressive Sensing has some obvious bearing on some of these challenges, to name a few I'd go for 6, 7, 8, 10 and 15.

Mathematical Challenge One: The Mathematics of the Brain

• Develop a mathematical theory to build a functional model of the brain that is mathematically consistent and predictive rather than merely biologically inspired.

Mathematical Challenge Two: The Dynamics of Networks

• Develop the high-dimensional mathematics needed to accurately model and predict behavior in large-scale distributed networks that evolve over time occurring in communication, biology and the social sciences.

Mathematical Challenge Three: Capture and Harness Stochasticity in Nature

• Address Mumford’s call for new mathematics for the 21^st century. Develop methods that capture persistence in stochastic environments.

Mathematical Challenge Four: 21st Century Fluids

• Classical fluid dynamics and the Navier-Stokes Equation were extraordinarily successful in obtaining quantitative understanding of shock waves, turbulence and solitons, but new methods are needed to tackle complex fluids such as foams, suspensions, gels and liquid crystals.

Mathematical Challenge Five: Biological Quantum Field Theory

• Quantum and statistical methods have had great success modeling virus evolution. Can such techniques be used to model more complex systems such as bacteria? Can these techniques be used to control pathogen evolution?
  

Mathematical Challenge Six: Computational Duality

• Duality in mathematics has been a profound tool for theoretical understanding. Can it be extended to develop principled computational techniques where duality and geometry are the basis for novel algorithms?

Mathematical Challenge Seven: Occam’s Razor in Many Dimensions

• As data collection increases can we “do more with less” by finding lower bounds for sensing complexity in systems? This is related to questions about entropy maximization algorithms.

Mathematical Challenge Eight: Beyond Convex Optimization

• Can linear algebra be replaced by algebraic geometry in a systematic way?

Mathematical Challenge Nine: What are the Physical Consequences of Perelman’s Proof of Thurston’s Geometrization Theorem?

• Can profound theoretical advances in understanding three dimensions be applied to construct and manipulate structures across scales to fabricate novel materials?

Mathematical Challenge Ten: Algorithmic Origami and Biology

• Build a stronger mathematical theory for isometric and rigid embedding that can give insight into protein folding.

Mathematical Challenge Eleven: Optimal Nanostructures

• Develop new mathematics for constructing optimal globally symmetric structures by following simple local rules via the process of nanoscale self-assembly.

Mathematical Challenge Twelve: The Mathematics of Quantum Computing, Algorithms, and Entanglement

• In the last century we learned how quantum phenomena shape our world. In the coming century we need to develop the mathematics required to control the quantum world.

Mathematical Challenge Thirteen: Creating a Game Theory that Scales

• What new scalable mathematics is needed to replace the traditional Partial Differential Equations (PDE) approach to differential games?

Mathematical Challenge Fourteen: An Information Theory for Virus Evolution

• Can Shannon’s theory shed light on this fundamental area of biology?

Mathematical Challenge Fifteen: The Geometry of Genome Space

• What notion of distance is needed to incorporate biological utility?
  

Mathematical Challenge Sixteen: What are the Symmetries and Action Principles for Biology?

• Extend our understanding of symmetries and action principles in biology along the lines of classical thermodynamics, to include important biological concepts such as robustness, modularity, evolvability and variability.

Mathematical Challenge Seventeen: Geometric Langlands and Quantum Physics

• How does the Langlands program, which originated in number theory and representation theory, explain the fundamental symmetries of physics? And vice versa?

Mathematical Challenge Eighteen: Arithmetic Langlands, Topology, and Geometry

• What is the role of homotopy theory in the classical, geometric, and quantum Langlands programs?

Mathematical Challenge Nineteen: Settle the Riemann Hypothesis

• The Holy Grail of number theory.

Mathematical Challenge Twenty: Computation at Scale

• How can we develop asymptotics for a world with massively many degrees of freedom?

Mathematical Challenge Twenty-one: Settle the Hodge Conjecture

• This conjecture in algebraic geometry is a metaphor for transforming transcendental computations into algebraic ones.

Mathematical Challenge Twenty-two: Settle the Smooth Poincare Conjecture in Dimension 4

• What are the implications for space-time and cosmology? And might the answer unlock the secret of “dark energy”?

Mathematical Challenge Twenty-three: What are the Fundamental Laws of Biology?

• This question will remain front and center for the next 100 years. DARPA places this challenge last as finding these laws will undoubtedly require the mathematics developed in answering several of the questions listed above.