Our everyday life is now the witness of a constant stream of large amount of data. (stocks market, medical diagnosis, social networks, geolocalization….), a situation that is new to our collective wisdom and is becoming overwhelming to our processing power. This new world of increasing complexity requires us to devise ever increasing processing hardware in order to make sense of this constant « deluge » of data. A recent subsampling technique, devised on theoretical ground only 6 years ago, called compressed sensing aims to do just that by changing the way we acquire data in the first place. I propose to use 48 cores to map the phase transition between what is and what is not feasible by this new kind of compressed sensing hardware.
I write a small blog on compressed sensing, a topic recently featured in Wired Magazine. In short, Compressed Sensing enables a new type of signal processing based on the often verified assumption that the underlying signal of interest (an image, a movie …) is sparse in some fashion or another. In this new field of investigation, David Donoho and Jared Tanner computed the following groundbreaking phase transition effect (see abstract of this article):
We review connections between phase transitions in high-dimensional combinatorial geometry and phase transitions occurring in modern high-dimensional data analysis and signal processing. In data analysis, such transitions arise as abrupt breakdown of linear model selection, robust data fitting or compressed sensing reconstructions, when the complexity of the model or the number of outliers increases beyond a threshold... These thresholds are important in each subject area: for linear modelling, they place hard limits on the degree to which the now-ubiquitous high-throughput data analysis can be successful; for robustness, they place hard limits on the degree to which standard robust fitting methods can tolerate outliers before breaking down; for compressed sensing, they define the sharp boundary of the undersampling/sparsity tradeoff curve in undersampling theorems.... We conducted an extensive computational experiment ... to test the hypothesis that these phase transitions are universal across a range of underlying matrix ensembles. We ran millions of linear programs ...; to the naked eye, the empirical phase transitions do not depend on the ensemble, and they agree extremely well with the asymptotic theory .....
Compressed sensing implementations in hardware sometimes require a complete shift in the way we think of sensors. For instance, one could conceivably use Nature as a means of imaging or multiplexing data in a framework amenable to compressed sensing. The fact is we are just at the beginning of a new revolution in sensors development.
For this reason, we are interested in using a 48 core system to map the phase transition for specific hardware implementation or random systems as featured by natural systems. The computation of this transition is intrinsically parallel. While initially the system will be run locally, we could expand its use to the rest of the compressed sensing community through a simple GUI.
No comments:
Post a Comment