Is there a Compressed Sensing Solution for the Financial Regulators ?

Looking at the low traffic of this past week, I would not be surprised that everybody is very much concerned about their 401K or equivalent retirement plans and feel a little powerless about the whole situation. It's a little bit like the Titanic, everyone knows how the story ends, but nobody wants to take their eyes away from this huge sinking boat.

When I see some of the financial engineering currently that were at play, I am a little bothered that if it were a technology used in the real world, it would have been shut down a long time ago. In Nuclear Engineering for instance, we spent so much effort, sophistication and money in having safe and reliable systems that it is mindbuggling to hear about the current domino effect and the inability of the regulators to pinpoints the real problems.

We hear a lot about the fact that CDSs, CDOs and other elements of the alphabetical sauce are contracts that are "difficult" to understand and that this uncertainty is at the center of the mother of all crises. We also hear about banks not trusting each other and how the central banks by lending liquidity are, maybe, making things harder. Yet in the end, there is a sense that some type of worldwide collaboration of different experts is probably the only way to give the beginning of an answer. We'll see on Monday. Irrespective, it looks as though, there is a challenge here that has not been talked about: What type of instruments should regulators have in order to be aware of how good or bad things are ?

Coming back to what put us in this mess, Steve Hsu provides us with a picture of the problem in this entry entitled Notional vs net: Complexity is our enemy, and if you are visual like me you'll understand right away why this is a thorny issue.


In all this, I am more than unsettled with the inability of regulators to clearly identify the areas that need specific control (even during the good times) and I wonder aloud if some of the dimension reduction and CS techniques that we are currently developing and using could not be used in the future to give a sense on bad or good things are to these regulators. Elements that point me in that direction include the following elements:

• it is a distributed system where some nodes could be required to have counters and other operators.
• for each of the nodes, the data being processed every day seems enormous
  
• there is a need for encryption so that the market and the actors of the market cannot understand the data, yet the final data can only be understood by the regulators.
• Could we asnwer the following questions: How does disconnecting some of the node change the underlying manifold ? What is a good manifold ?
  

Any other thoughts ?

CS: Unanswered questions in CS, Accelerated Dense Random Projections, Apprenticeship Learning Using LP, "Real" Slepian-Wolf Codes

A summary of a talk at the SLIM lab on compressive sensing can be found in a blog entry entitled: Unanswered questions in compressed sensing

Edo Liberty has submitted his Ph.D. thesis entitled: Accelerated Dense Random Projections. The slides of the talk are here. When we met at Texas A&M, I asked Justin Romberg about the relationship between the random projections used in CS and those appearing from the Johnson-Lindenstrauss Lemma. He proceeded to give an explanation similar to the one he wrote in one of his paper entitled: Compressive sensing by random convolution where in page 7 of that paper, we can read:

In [1], Ailon and Chazelle propose the idea of a randomized Fourier transform followed by a random projection as a "fast Johnson-Lindenstrauss transform" (FJLT). The transform is decomposed as QF\Sigma, where Q is a sparse matrix with non-zero entries whose locations and values are chosen at random locations. They show that this matrix QF\Sigma behaves like a random waveform matrix in that with extremely high probability, it will not change the norm of an arbitrary vector too much. However, this construction requires that the number of non-zero entries in each row of Q is commensurate with the number of rows m of Q. Although ideal for dimensionality reduction of small point sets, this type of subsampling does not translate well to compressive sampling, as it would require us to randomly combine on the order of m samples of Hx_0 from arbitrary locations to form a single measurement -- taking m measurements would require on the order of m^2 samples. We show here that more structured projections, consisting either of one randomly chosen sample per row or a random combination of consecutive samples, are adequate for CS. This is in spite of the fact that our construction results in much weaker concentration than the FJLT.

That cleared it up but I think I needed to see it in writing :).

There is also a larger version of Compressive Structured Light for Recovering Inhomogeneous Participating Media, by Jinwei Gu, Shree Nayar, Eitan Grinspun, Peter Belhumeur, and Ravi Ramamoorthi

As some of you know, I am interested in policy learning, it is happens that Umar Syed, Robert Schapire, and Michael Bowling have just released Apprenticeship Learning Using Linear Programming. (web page). The abstract reads:

In apprenticeship learning, the goal is to learn a policy in a Markov decision process that is at least as good as a policy demonstrated by an expert. The difficulty arises in that the MDP's true reward function is assumed to be unknown. We show how to frame apprenticeship learning as a linear programming problem, and show that using an off-the-shelf LP solver to solve this problem results in a substantial improvement in running time over existing methods -- up to two orders of magnitude faster in our experiments. Additionally, our approach produces stationary policies, while all existing methods for apprenticeship learning output policies that are "mixed", i.e. randomized combinations of stationary policies. The technique used is general enough to convert any mixed policy to a stationary policy.

The video of the ICML presentation on the same subject is here.

Found on arxiv, two papers:

"Real" Slepian-Wolf Codes by Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg. The abstract reads:

We provide a novel achievability proof of the Slepian-Wolf theorem for i.i.d. sources over finite alphabets. We demonstrate that random codes that are linear over the real field achieve the classical Slepian-Wolf rate-region. For finite alphabets we show that typicality decoding is equivalent to solving an integer program. Minimum entropy decoding is also shown to achieve exponentially small probability of error. The techniques used may be of independent interest for code design for a wide class of information theory problems, and for the field of compressed sensing.

Large Scale Variational Inference and Experimental Design for Sparse Generalized Linear Models by Matthias W. Seeger and Hannes Nickisch. The abstract reads

We provide novel approximate Bayesian inference algorithms for sparse generalized linear models, that can be used with hundred thousands of variables, and run orders of magnitude faster than previous algorithms in domains where either apply. By analyzing our methods and establishing some novel convexity results, we settle a long-standing open question about variational Bayesian inference for continuous variable models: the Gaussian lower bound relaxation, which has been used previously for a range of models, is proved to be a convex optimization problem, if and only if the posterior mode is found by convex programming. Our algorithms reduce to the same computational primitives than commonly used sparse estimation methods do, but require Gaussian marginal variance estimation as well.
We are interested in Bayesian experimental design here (which is mainly driven by efficient approximate inference), a powerful framework for optimizing measurement architectures of complex signals, such as natural images. Designs optimized by our Bayesian framework strongly outperform choices advocated by compressed sensing theory, and with our novel algorithms, we can scale it up to full-size images. Immediate applications of our method lie in digital photography and medical imaging.

Photo Credit: EUMETSAT. Meteosat-8 Rapid Scan captures asteroid impact, On 7 October, asteroid 2008 TC3 hit Earth and exploded in the atmosphere over northern Sudan. Amazingly, the Meteosat-8 Rapid Scanning Service managed to capture the impact.

CS Community: Impact, Google adwords failing for low volume terms and Intel Research

This week shows an unusual low traffic, I wonder if there is something unusual going on... nah... Talking about traffic, as you know I am trying to gauge the impact of the site. I looked at the web hits of the Seismic Laboratory for Imaging and Modeling (SLIM) at University of British Columbia that hosts the paper I mentioned yesterday: Compressive simultaneous full-waveform simulation by Felix Herrmann, Yogi Erlangga and Tim Lin and it looks like the site served the file 50 times yesterday (from zero the day before). This is great.




There are two or three people at Google reading this blog. This is for them: I have continued the experiment mentioned earlier, but this is what I am getting (see below) how do you explain that the term "Compressive Sensing" has a poor score whereas "Compressed Sensing" doesn't?

This is all the more interesting as the CTR for "Compressive Sensing" is higher than for "Compressed Sensing" ?


In other news, Intel Research in Seattle had an Open house on October 1st, 2008. There is a mention of compressive sensing in their brochure. Here are some of their projects.

CS: Compressed Counting, Data Stream Algorithms videos

This entry has a more Theoretical Computer Science (TCS) flavor to it:


Ping Li has released his latest paper on Compressed Counting. We mentioned a presentation on that subject and other work before.

Graham Cormode did a presentation/tutorial on Data stream algorithms last July. It was a tutorial presented at the Bristol Summer School on Probabilistic Techniques in Computer Science.

Many scenarios, such as network analysis, utility monitoring, and financial applications, generate massive streams of data. These streams consist of millions or billions of simple updates every hour, and must be processed to extract the information described in tiny pieces. These notes provide an introduction to (and set of references for) data stream algorithms, and some of the techniques that have been developed over recent years to help mine the data while avoiding drowning in these massive flows of information.

The video is here. The ppt slides are here while the pdf slides are here.

All the other videos of that meeting can be found here. It includes talks by:

• Ayalvadi Ganesh, on Random Graphs and Stochastic Processes
• Eyal Kushilevitz, on Communication Complexity.
• S. Muthu Muthukrishnan, on Auction Theory for Sponsored Search
• Joseph Naor, on Approximation Algorithms.
• Andreas Winter, on Concentration of Measure.
• Bella Bollobas, on Inhomogeneous Random Graphs

On a totally unrelated subject, my webcrawler only goes through publication pages. If you have an opening for a post that requires some understanding of compressive sensing and related matter, do not hesitate to let me know.



Credit: NASA/Johns Hopkins University Applied Physics Laboratory/Carnegie Institution of Washington, Mercury as never seen before. Image taken the day before yesterday (October 6th) by the Messenger spacecraft.

CS: Compressive simultaneous full-waveform simulation, SampTA '09 and a talk

Felix Herrmann, Yogi Erlangga and Tim Lin have released a technical report on Compressive simultaneous full-waveform simulation. The abstract reads:

The fact that the numerical complexity of wavefield simulation is proportional to the size of the discretized model and acquisition geometry, and not to the complexity of the simulated wavefield, is the main impediment within seismic imaging. By turning simulation into a compressive sensing problem---where simulated data is recovered from a relatively small number of independent simultaneous sources---we remove this impediment by showing that compressively sampling a simulation is equivalent to compressively sampling the sources, followed by solving a reduced system. As in compressive sensing, this allows for a reduction in sampling rate and hence in simulation costs. We demonstrate this principle for the time-harmonic Helmholtz solver. The solution is computed by inverting the reduced system, followed by a recovery of the full wavefield with a sparsity promoting program. Depending on the wavefield's sparsity, this approach can lead to significant cost reductions, in particular when combined with the implicit preconditioned Helmholtz solver, which is known to converge even for decreasing mesh sizes and increasing angular frequencies. These properties make our scheme a viable alternative to explicit time-domain finite-differences.

Jared Tanner just mentioned to me the organization of a meeting called SampTA '09 in Marseilles, France.

The purpose of SAMPTA's is to bring together mathematicians and engineers interested in sampling theory and its applications to related fields (such as signal and image processing, coding theory, control theory, complex analysis, harmonic analysis, differential equations) to exchange recent advances and to discuss open problems.

SAMPTA09 will be organized around plenary lectures, general sessions on sampling and applications, and special sessions on selected topics. Ample time will be left for discussions. The topics of the special sessions are the following:Compensation of channel mismatch errors in time-interleaved analog-to-digital converters, Compressed sensing, Mathematical aspects of compressed sensing, Frame theory and oversampling, Geometric multiscale analysis, Sampling and quantization, Sampling and communication, Sampling and painting, Sampling and industrial applications, Sampling using finite rate of innovation principles, Sparse approximation and high-dimensional geometry, and Super-resolution.

Submissions will be reviewed. Please notice the following important dates:

* January 15, 2009: Deadline for paper submission.
* February 15, 2009: Notification of paper acceptance.
* April 15, 2009: Deadline for final paper submission and registration

Martin Vetterli will give a talk at Columbia on October 22. The title of the talk is Sparse Sampling: Variations on a Theme by Shannon

The last two items are listed in the Compressive Sensing Calendar.

CS: The Secrecy of CS Measurements, Counting faces of randomly-projected polytopes, Compressive wireless arrays, Compressive beamforming and Mapping.

Here is a paper by Yaron Rachlin and Dror Baron on The Secrecy of Compressive Sensing Measurements that is evaluating whether it is possible to estimate the measurement matrix when one is given the final CS measurements. Dror and Yaron have also gone through the pain of explaining the paper in a more user-friendly summary than an abstract, I am grateful for that and I am copying verbatim their commentary (Thanks Dror and Yaron!).

Several recent papers mention the possibility that compressed sensing measurements are encrypted. In this paper, we investigate this claim. We consider a scenario where Alice has a secret message (in our model the message is a real, K-sparse signal) that she would like to share with Bob. She encodes this signal using an M by N Gaussian measurement matrix. Bob receives the measurements, and can recover the signal, because he also knows the measurement matrix (in practice, Alice and Bob could share the seed of a random number generator used to produce
the measurement matrix). Can an eavesdropper (Eve), who intercepts the measurements, recover the signal without knowing the measurement matrix? We evaluate this question using two well-established approaches to encryption: information-theoretic and computational.

First, we consider the stronger information-theoretic notion of perfect secrecy. This notion requires the mutual information between signals and measurements to be zero. However, the signals and measurements are statistically dependent, which rules out perfect secrecy. Second, we consider the weaker notion of computational secrecy, which means that Eve can only recover the signal with a prohibitively large computational cost. We prove that compressed sensing achieves a computational notion of secrecy in the face of an adversary attempting to use either ell_0 or ell_1 minimization. Our result hinges on a theorem that shows that with probability one Eve will recover an M-sparse explanation instead of a K-sparse explanation when using the wrong measurement matrix.

The abstract itself reads:

Results in compressed sensing describe the feasibility of reconstructing sparse signals using a small number of linear measurements. In addition to compressing the signal, do these measurements provide secrecy? This paper considers secrecy in the context of an adversary that does not know the measurement matrix used to encrypt the signal. We demonstrate that compressed sensing based encryption does not achieve Shannon’s definition of perfect secrecy, but can provide a computational guarantee of secrecy.

Here is a paper in which some of the findings were presented by Jared Tanner at Texas A&M: David Donoho and Jared Tanner in Counting faces of randomly-projected polytopes when the projection radically lowers dimension. The first part of the introduction reads:

1.1. Three surprises of high dimensions. This paper develops asymptotic methods

to count faces of random high-dimensional polytopes; a seemingly dry and unpromising pursuit. Yet our conclusions have surprising implications - in statistics,

probability, information theory, and signal processing - with potential impacts in

practical subjects like medical imaging and digital communications. Before involving

the reader in our lengthy analysis of high-dimensional face counting, we describe

three implications of our results.

• 1.1.1 Convex Hulls of Gaussian Point Clouds.
  
• 1.1.2. Signal Recovery from Random Projections.
  
• 1.1.3. How many gross errors can we efficiently correct?
  

Also found are three more papers from the Rice Compressed Sensing Resources:

Volkan Cevher, Ali Gurbuz, James McClellan, and Rama Chellappa, Compressive wireless arrays for bearing estimation of sparse sources in angle domain. The abstract reads:

Joint processing of sensor array outputs improves the performance of parameter estimation and hypothesis testing problems beyond the sum of the individual sensor processing results. When the sensors have high data sampling rates, arrays are tethered, creating a disadvantage for their deployment and also limiting their aperture size. In this paper, we develop the signal processing algorithms for randomly deployable wireless sensor arrays that are severely constrained in communication bandwidth. We focus on the acoustic bearing estimation problem and show that when the target bearings are modeled as a sparse vector in the angle space, functions of the low dimensional random projections of the microphone signals can be used to determine multiple source bearings as a solution of an ℓ1-norm minimization problem. Field data results are shown where only 10bits of information is passed from each microphone to estimate multiple target bearings.

Ali Gurbuz, James McClellan, and Volkan Cevher, A compressive beamforming method. The abstract reads:

Compressive Sensing (CS) is an emerging area which uses a relatively small number of non-traditional samples in the form of randomized projections to reconstruct sparse or compressible signals. This paper considers the direction-of-arrival (DOA) estimation problem with an array of sensors using CS. We show that by using random projections of the sensor data, along with a full waveform recording on one reference sensor, a sparse angle space scenario can be reconstructed, giving the number of sources and their DOA’s. The number of projections can be very small, proportional to the number sources. We provide simulations to demonstrate the performance and the advantages of our compressive beamformer algorithm.

Yasamin Mostofi and Pradeep Sen, Compressed mapping of communication signal strength. The abstract reads:

In this paper we consider a mobile cooperative network that is tasked with building a map of the received signal strength to a fixed station. By using the recent results in the area of compressed sensing, we show how the nodes can exploit the sparse representation of the channel’s spatial variations to build a map of the signal strength with minimal sensing. We furthermore propose a successive interference cancellation method for signal reconstruction based on a considerably incomplete set of measurements. The proposed method is an extension of the existing signal reconstruction strategies but with a considerably better performance. Finally, we present simulation results that show the performance of the proposed framework.

Credit: NASA/JPL/University of Arizona, Unconformity in Mars North Polar Layered Deposits (PSP_009390_2595) as taken by the HiRiSE camera

CS: Impact statistics - part deux.

This entry is an update to a previous post on readership statistics as we crossed the 6,000 visits in September. I have listed the previous month's stats next to the August numbers.

Currently, in order to provide information to this blog and attendant pages:

• there are about 500 pages being crawled every day,
• I have on average between one and two good discussions with one of you or a researcher outside of this community on the subject of compressive sensing per week.
• There have been about 306 (prev. 286) entries on Compressive Sensing, most of them featuring extremely recent preprints.
  

On the readership's side:

• ~34 (prev. ~30) people are reading this blog directly in their e-mail box,
• 112 (prev. 102) people are reading this blog through Google Reader, while another 75 (prev. 60) maybe reading this RSS feed thanks to Feedburner.
  
• ~ 218 (prev. ~180) visitors/day or about ~6500 (prev. ~5000) visitors/months (not unique) are coming to the site with about half of that traffic from the search engines and from wikipedia. The other half is people who are reading the blog through an RSS reader and who want to look at past entries.
  
• The Compressive Sensing LinkedIn group has 53 (prev. 24) members since its inception a month and a week ago.
• The readership and linkage to Nuit Blanche have enabled it to reach a PageRank of 5, while the Big Picture site has a PageRank of 3.
  
• Some people come back often to either the blog or to the Big Picture site and some people stay for long periods of time (see the stats below gathered over a year and a half time period)
  

On the impact side, I have had some widely differing accounts. This mostly stems from the fact that:

• I link directly to papers and Google Analytics or some other counters do not do a good job at counting those hits,
• Sometimes Nuit Blanche is not the only blog/site pointing to the page or paper, hence it is difficult to find out the source of the increase in traffic.
  
• People read the blog through e-mails, rss readers, Google cache or through the site itself, I can see only certain types of click-through to the papers.
  

For all these reasons, I currently estimate that about 60 to 100 (same as previous as I don't have a better way of doing this statistics) people will click through to the paper listed on the blog the day it is posted. I also estimate that over time that number is doubled. But the most important thing to remember is that once it is featured either on the Rice Compressive Sensing repository page or on this blog, Google knows about it and it becomes visible much before it eventually is published on a journals' sites.

CS: Convex Iteration Reconstruction Technique, Gradient based method for cone programming with application to large-scale compressed sensing

Today, we have two new reconstruction techniques with their attendant Matlab codes. The first algorithm seems to be fast and doing better in terms of the number of CS measurements needed to reconstruct a known benchmark, the second algorithm seems to be very fast compared to Interior Point algorithms.

Jon Dattorro forwarded me an excerpt of his book on Convex Optimization [1] where he described another reconstruction algorithm he calls Convex Iteration. The part of interest is located in Chapter 4 page 306 to 314. Jon also mentioned to me:

The most salient results of the paper comprise the Convex Iteration method for minimizing cardinality, and a new lower bound of 2% on image-gradient cardinality for the 256x256 Shepp-Logan phantom from the Matlab Image Processing Toolbox. Previously believed to be 3%, this new lower bound is a consequence of an adaptive strategy for computing image-gradient; specifically, the algorithm assumes that number of pixels (between 1 and 4), involved in an image-gradient estimation, is variable.


The Matlab code that realizes the algorithm (available here) is exceedingly fast by comparison with other contemporary methods. It runs on a laptop in a Matlab minute; its speed due, in large part, to Josh Trzasko at Mayo Clinic.

I very much like Jon's basic explanations in his book. He previously gave an earlier similar clear explanation in "Trace: What is it good for ? - How Compressed Sensing relates to Dimensionality Reduction".

The second algorithm is devised by Zhaosong Lu in Gradient based method for cone programming with application to large-scale compressed sensing. The abstract reads:

In this paper, we study a gradient based method for general cone programming (CP) problems. In particular, we first consider four natural primal-dual convex smooth minimization reformulations for them, and then discuss a variant of Nesterov’s smooth (VNS) method recently proposed by Tseng [30] for solving these reformulations. The associated worst-case major arithmetic operations costs of the VNS method for them are estimated and compared. We show that for a class of CP problems, the VNS method based on the last reformulation generally outperforms that applied to the others. Finally, we discuss the application of the VNS method [30] to some large-scale CP problems arising in compressed sensing, which are highly challenging to simplex and/or interior point (IP) methods. The performance of this method is compared with the IP method [4] that is specially implemented for these problems. Our computational results demonstrate that for these CP problems, the VNS method [30] applied to the mostly suitable reformulation mentioned above substantially outperforms the IP method [4].

The attendant Matlab source codes are here.

These algorithms as well as those mentioned yesterday are listed in the reconstruction section of the Big Picture.


Reference: [1] Convex Optimization & Euclidean Distance Geometry by Jon Dattorro

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.

CS: Tilings, Islamic Art, Our Retina, Papoulis Sub-Nyquist Theorem

[Note: This is an open ended entry, sorry, I am trying to put these pieces together ]

As a I was re-reading Yves Meyer's recent presentation entitled: Compressed sensing and transference (the paper is here "A variant of compressed sensing "), I also came across his reference to some Islamic Art. If you recall, Yves Meyer has looked at quasicrystals tiling and has seen a connection with how to sample a positive function and reconstruct it with a linear programming step. It so happens that the connection between quasicrystals and Islamic art was made by Peter Lu as a hobby while being a graduate student. He has a beautiful video presentation on the subject of Quasicrystals in Medieval Islamic Architecture.

I liked the connection to the non-sticking pan material that messes up the phonon transport. At 45 minutes in the presentation, Paul begins to explain the non-periodic aspect of these tilings and the last question by a person in the audience is potentially of interest when it comes to sampling on manifolds.

The Science paper is here and the additional material is here. Paul Steinhardt the co-author of the study has a webpage on the tiling description and goes on to say in the "implications" section:

The new paradigm implies a closer physical relationship between quasicrystals and crystals. Now it appears that both can be described in terms of the close-packing of a single cluster or unit cell. In a crystal, the unit cell packs edge-to-edge with its neighbors. Quasicrystals correspond to a generalization in which the quasi-unit cells overlap. In both cases, the formation of the particular structure appears to be explained by a low-energy atomic cluster, although the atomic arrangement in the case of quasicrystals is constrained to allow overlap. Hence, the new paradigm makes plausible why many materials form quasicrystals and, at the same time, explains why quasicrystals are less common than crystals.....The new paradigm requires a mechanism to explain how quasicrystals grow. If the quasicrystals are grown slowly, then thermodynamic relaxation to the ground state is possible. However, some of the most perfect quasicrystal samples, including AlNiCo , are formed by rapid quenching. In this volume, Socolar has described a scheme for solids equivalent to Penrose patterns based on obtuse and acute rhombi using vertex rules and stochastic growth similar to diffusion limited aggregation. This approach can be adapted to overlapping clusters. (Janot[13] has already suggested a similar mechanism for overlapping clusters, although his vertex rules allow random tilings as well as perfect quasiperiodic tilings.) If quasicrystals form due to a particular cluster being energetically favored, a simpler kinematic mechanism may be through local atomic rearrangement that increases the local density of the given atomic cluster.

Hmmm, so we don't have a good way of explaining away the difference between random tilings and quasicrystal ones. Looks like we have a similar issue in compressive sampling where the connection between the tiling of Yves Meyer and Basarab Matei is not well connected to the generic random projections used in generic compressive sensing (expect maybe through the suggestion of Thong Do, Trac Tran and Lu Gan to include them in Structurally Random Matrices approach, in this case the analog FFT is performed by the lens). Furthermore, we also still have to characterize if our own pixel tiling located in our retina is also really that random as seen in these exceptional shots from Austin Roorda at Berkeley [17].

where it can be noted some type of hexagonal tiling in the Fourier world [16]

While reading these papers, a paper by Yue M. Lu, Minh Do and Richard Laugesen came out. It is entitled:



A computable Fourier condition generating alias-free sampling lattices. The abstract reads:

We propose a Fourier analytical condition linking alias-free sampling with the Fourier transform of the indicator function defined on the given frequency support. Our discussions center around how to develop practical computation algorithms based on the proposed analytical condition. We address several issues along this line, including the derivation of simple closed-form expressions for the Fourier transforms of the indicator functions defined on arbitrary polygonal and polyhedral domains; a complete and nonredundant enumeration of all quantized sampling lattices via the Hermite normal forms of integer matrices; and a quantitative analysis of the approximation of the original infinite Fourier condition by using finite computations. Combining these results, we propose a computational testing procedure that can efficiently search for the optimal alias-free sampling lattices for a given polygonal or polyhedral shaped frequency domain. Several examples are presented to show the potential of the proposed algorithm in multidimensional filter bank design, as well as in applications involving the design of efficient sampling patterns for multidimensional bandlimited signals.

an extract of this paper reads:

On a broader scale, alias-free sampling is mathematically equivalent to the lattice packing of a given domain, for which lots of studies can be found in disciplines such as computational geometry and operational research. So far, most practical algorithms proposed for densest lattice packing (e.g. [14]–[16]) approach the problem from a geometrical perspective. The primary tools employed are the theories from Minkowski’s work [13], as well as various geometrical intuitions and heuristics obtained for particular domains in lower dimensions......Before proceeding, we make some remarks on the scope of this paper. First, we restrict our attention to the scenario in which the continuous signals are sampled on a single lattice. Consequently, the minimum sampling rate we pursue is the Nyquist rate, which is achieved by those lattices that can pack the frequency support D in the tightest way. We note that it is possible to go below the Nyquist rate if we can sample the continuous signals with multiple channels and on multiple lattices (see, e.g., [19], [20]).

Let us recall that the subdivision scheme in the quasicrystal presentation seem to clearly fall under the class of multiple lattices. When doing a search on the IEEE xplore database reference 1 through 15 show up when refering to the 1977 Papoulis' Generalized sampling expansion [5]. I note a hardware based on this sub-nyquist sampling approach in [15]. I still cannot make much of it, so if somebody has an insight, I would gladly welcome it.

Talking about Compressive Sampling, the Computer Science Department at University of Alberta has a reading group on the subject.

References:

1. On well-posedness of the Papoulis generalized sampling expansion, Brown, J.L., Jr.; Cabrera, S.D.; Circuits and Systems, IEEE Transactions on, Volume 38, Issue 5, May 1991 Page(s):554 - 556

2. Generalized sampling expansion on lattices, Izen, S.H.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on], Volume 53, Issue 6, June 2005 Page(s):1949 - 1963

3. Optimal generalized sampling expansion, Seidner, D.; Feder, M.; Acoustics, Speech, and Signal Processing, 1999. ICASSP '99. Proceedings., 1999 IEEE International Conference on, Volume 3, 15-19 March 1999 Page(s):1637 - 1640 vol.3

4. On the necessity of Papoulis' result for multidimensional GSE, Feuer, A.; Signal Processing Letters, IEEE. Volume 11, Issue 4, April 2004 Page(s):420 - 422

5. Generalized sampling expansion, Papoulis, A.; Circuits and Systems, IEEE Transactions on, Volume 24, Issue 11, Nov 1977 Page(s):652 - 654

6. Extension of a finite version of the sampling theorem, De Sabata, A.; Circuits and Systems II: Analog and Digital Signal Processing, IEEE Transactions on. Volume 41, Issue 12, Dec. 1994

7. Incomplete sampling series and the recovery of missing samples from oversampled band-limited signals, Ferreira, P.J.S.G.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on]
Volume 40, Issue 1, Jan. 1992 Page(s):225 - 227

9. Filterbank reconstruction of bandlimited signals from nonuniform and generalized samples, Eldar, Y.C.; Oppenheim, A.V.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on, Volume 48,
Issue 10, Oct. 2000 Page(s):2864 - 2875

10. Vector sampling expansion, Seidner, D.; Feder, M.; Signal Processing, IEEE Transactions on [see also Acoustics, Speech, and Signal Processing, IEEE Transactions on] Volume 48, Issue 5, May 2000 Page(s):1401 - 1416

11. Filter bank interpolation and reconstruction from generalized and recurrent nonuniform samples, Eldar, Y.C.; Oppenheim, A.V.; Acoustics, Speech, and Signal Processing, 2000. ICASSP '00. Proceedings. 2000 IEEE International Conference on, Volume 1, 5-9 June 2000 Page(s):324 - 327 vol.1

12. 3D super-resolution using generalized sampling expansion, Shekarforoush, H.; Berthod, M.; Zerubia, J.; Image Processing, 1995. Proceedings., International Conference on, Volume 2, 23-26 Oct. 1995 Page(s):300 - 303 vol.2

13. Sampling reconstruction of N-dimensional band-limited images after multilinear filtering, Brown, J.L., Jr.; Sa-ngsari, K.; Circuits and Systems, IEEE Transactions on Volume 36, Issue 7, July 1989 Page(s):1035 - 1038

14. On generalized sampling expansions for deterministic signals, Figueiras-Vidal, A.; Marino-Acebal, J.; Gomez, R.; Circuits and Systems, IEEE Transactions on Volume 28, Issue 2, Feb 1981 Page(s):153 - 154

15. Sampling below the Nyquist rate in interferometric fluorescence microscopy with multi-wavelength measurements to remove aliasing, Davis, B.J.; Karl, W.C.; Goldberg, B.B.; Swan, A.K.; Unlu, M.S.; Digital Signal Processing Workshop, 2004 and the 3rd IEEE Signal Processing Education Workshop. 2004 IEEE 11th, 1-4 Aug. 2004 Page(s):329 - 333

16. Duncan,J.L., Zhang,Y., Gandhi,J., Nakanishi,C., Othman,M., Branham,K.H., Swaroop,A., Austin Roorda High resolution imaging of foveal cones in patients with inherited retinal degenerations using adaptive optics, Invest.Ophthalmol.Vis.Sci. 48: 3283-3291 (2007)

17. Austin Roorda, A., Williams, D.R., The Arrangement of the Three Cone Classes in the Living Human Eye Nature 397, 520-522 (1999).