Nuit Blanche community
@NuitBlog || Facebook (413) || Reddit (2369)
Compressive Sensing on LinkedIn (3978)
Advanced Matrix Factorization on Linkedin (1326)||
The Advanced Matrix Factorization Jungle Page ||
Friday, August 31, 2007
I just used Freemind to produce a map of most of the entries on Compressed Sensing I have written so far. It should help in the navigation, I'll update as we go. It is here. The freemind file is here. The reverse chronological order is shown here.Please note that I made it a permanent link on the right side bar so that one can jump into it right away when coming to this blog. The map of entries is here: http://igorcarron.googlepages.com/compressedsensing
while the blog with items marked Compressed Sensing is here: http://nuit-blanche.blogspot.com/search/label/compressed%20sensing
Thursday, August 30, 2007
- An introduction to transform coding , Lecture 1 Slides (pdf)
- Compressive sensing for time signals: Analog to information conversion, Lecture 2 Slides (pdf), Talks(A/V) (ram)
- Compressive sensing for detection and classification problems ,Lecture 3 Slides (pdf), Talks(A/V) (ram)
- Multi-signal, distributed compressive sensing Lecture 4 Slides (pdf), Talks(A/V) (ram)
- Compressive imaging with a single pixel camera Lecture 5 Slides (pdf), Talks(A/V) (ram)
- Sparsity, Talks(A/V) (ram)
- After a rapid and glossy introduction to compressive sampling–or compressed sensing as this is also called–the lecture will introduce sparsity as a key modeling tool; the lecture will review the crucial role played by sparsity in various areas such as data compression, statistical estimation and scientific computing.
- Sparsity and the l1 norm, Talks(A/V) (ram)
- In many applications, one often has fewer equations than unknowns. While this seems hopeless, we will show that the premise that the object we wish to recover is sparse or compressible radically changes the problem, making the search for solutions feasible. This lecture discusses the importance of the l1-norm as a sparsity promoting functional and will go through a series of examples touching on many areas of data processing.
- Compressive sampling: sparsity and incoherence , Talks(A/V) (ram)
- Compressed sensing essentially relies on two tenets: the first is that the object we wish to recover is compressible in the sense that it has a sparse expansion in a set of basis functions; the second is that the measurements we make (the sensing waveforms) must be incoherent with these basis functions. This lecture will introduce key results in the field such as a new kind of sampling theorem which states that one can sample a spectrally sparse signal at a rate close to the information rate---and this without information loss.
- The uniform uncertainty principle, Talks(A/V) (ram)
- We introduce a strong form of uncertainty relation and discuss its fundamental role in the theory of compressive sampling. We give examples of random sensing matrices obeying this strong uncertainty principle; e.g. Gaussian matrices.
- The role of probability in compressive sampling, Talks(A/V) (ram)
- This lecture will discuss the crucial role played by probability in compressive sampling; we will discuss techniques for obtaining nonasymptotic results about extremal eigenvalues of random matrices. Of special interest is the role played by high- dimensional convex geometry and techniques from geometric functional analysis such as the Rudelson's selection lemma and the role played by powerful results in the probabilistic theory of Banach space such as Talagrand's concentration inequality.
- Robust compressive sampling and connections with statistics, Talks(A/V) (ram)
- We show that compressive sampling is–perhaps surprisingly–robust vis a vis modeling and measurement errors.
- Robust compressive sampling and connections with statistics (continued) Talks(A/V) (ram)
- We show that accurate estimation from noisy undersampled data is sometimes possible and connect our results with a large literature in statistics concerned with high dimensionality; that is, situations in which the number of observations is less than the number of parameters.
- Connections with information and coding theory Talks(A/V) (ram)
- We morph compressive sampling into an error correcting code, and explore the implications of this sampling theory for lossy compression and some of its relationship with universal source coding.
- Modern convex optimization Talks(A/V) (ram)
- We will survey the literature on interior point methods which are very efficient numerical algorithms for solving large scale convex optimization problems.
- Applications, experiments and open problems Talks(A/V) (ram)
- We discuss several applications of compressive sampling in the area of analog-to-digital conversion and biomedical imaging and review some numerical experiments in new directions. We conclude by exposing the participants to some important open problems
- Signal encoding Lecture 1 Slides (pdf), Talks(A/V) (ram)
- Shannon-Nyquist Theory, Pulse Code Modulation, Sigma-Delta Modulation, Kolmogorov entropy, optimal encoding.
- Compression Lecture 2 Slides (pdf), Talks(A/V) (ram)
- Best k-term approximation for bases and dictionaries, decay rates, approximation classes, application to image compression via wavelet decompositions.
- Discrete compressed sensing , Lecture 3 Slides (pdf), Talks(A/V) (ram)
- The problem, best matrices for classes, Gelfand widths and their connection to compressed sensing.
- The restricted isometry property (RIP) , Talks(A/V) (ram)
- Performance of compressed sensing under RIP.
- Construction of CS matrices with best RIP , Talks(A/V) (ram)
- Bernoulli and Gaussian random variables.
- Performance of CS matrices revisited Lecture 6 Slides (pdf), Talks(A/V) (ram)
- Proofs of the Kashin-Gluskin theorems.
- Performance in probability, Lecture 7 Slides (pdf), Talks(A/V) (ram)
- Examples of performance for Gaussian and Bernoulli ensembles.
- Decoders , Lecture 8 Slides (pdf), Talks(A/V) (ram)
- l1 minimization, greedy algorithms, iterated least squares.
- Performance of iterated least squares Paper (pdf), Talks(A/V) (ram)
- Convergence and exponential convergence.
- Deterministic constructions of CS Matrices , Lecture 10 Slides (pdf), Talks(A/V) (ram)
- Constructions from finite fields, circulant matrices.
- Algorithms for Compressed Sensing, I Slides (pdf), Talks(A/V) (ram)
- What algorithmic problem do we mean by Compressed Sensing? There are a variety of alternatives, each with different algorithmic solutions (both theoretical and practical). I will discuss some of the different types of results from the combinatorial to the probabilistic.
- Algorithms for Compressed Sensing, II Lecture notes (pdf) , Talks(A/V) (ram)
- What do these algorithms all have in common? What are the common goals of the problems and how do they achieve them? I will discuss several known techniques and open problems.
- Welcome and introduction, Talks(A/V) (ram)
Leon Axel (New York University)
, Steen Moeller (University of Minnesota)
Short presentations by participants Short presentation by participants (A/V) (ram)
Discussion (A/V) (ram)
Discussion (A/V) (ram)
Short presentations by participants
- Short presentation by participants 1 (ram)
- Short presentation by participants 2 (ram)
- Short presentation by participants 3 (ram)
- Short presentation by participants 4 (ram)
- Short presentation by participants 5 (ram)
Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from
If you think this blog provides a service, please support it by ordering through the Amazon - Nuit Blanche Reference Store
Wednesday, August 29, 2007
The presentation are available on the MADALGO summer school website, a very nice initiative:
- Piotr Indyk: Introduction. Norm/Count estimation.
- Sudipto Guha: Metric data. Clustering. Graph data.
- Piotr Indyk: Geometric data. Clustering. MST.
- T.S. Jayram: Intro to lower bounds, communication complexity.
- Sudipto Guha: Random order streams.
- Ravi Kumar: Lower bounds 1 + 2.
- Martin Strauss: Heavy hitters. Wavelets and histograms.
- Martin Strauss: Compressed sensing, LP-based decoding, & Combinatorial decoding.
We all know about the Rice Compressed Sensing library that gathers all papers/links of papers relevant to Compressed Sensing. I just found out they also have a chronological listing. The Overview has also changed to reflect a better definition of Compressed Sensing. It includes:
Compressive sensing is also referred to in the literature by the terms: compressed sensing, compressive sampling, and sketching/heavy-hitters.and features not only papers but also links to (mostly) Matlab Toolbox for Compressed Sensing.
Tuesday, August 28, 2007
When I saw these graphs, I could not but notice the following, there seems to be a resonance when the maximum temperature goes above 35 C (35 degree Celsius = 95 degree Fahrenheit). The average body temperature is 37 degree Celsius (or 98.6 degree Fahrenheit), skin temperature is an average of 34 C and we also know that water is very anomalous, and in particular that the specific heat capacity (CP) has a minimum at 36°C.
One can always imagine the following, between 34C and 37 C, the body (made of 90 % water) starts taking in heat from the surrounding (mainly from radiation) and it does so more quickly at around 36 C. Since, we are only accustomed to heat warming the body slowly at lower temperature (higher Cp at T less than 30 C), there is a compounding effect taking place above 34 C that yields catastrophes on populations not accustomed to these heat fluxes. One also wonder, if a lower-tech version of DARPA cooling glove would not be an efficient tool in these situations (besides drinking and air conditioning).
 A predictive model relating daily fluctuations in summer temperatures and mortality rates.
Sunday, August 26, 2007
- How come we don't have Jurassic Park with walking dinosaurs ? everytime there is an animotronics coming in town, you have lines of kids waiting to see those things even if the time spent waiting will be longer than the time spent watching them and yet we still don't have walking dinosaurs (except when a human is inside). How come ? (my interest here lie in muscle, autonomous ). It looks as though we have only been able to devise their gait recently. Some people are already making a business case that building them will get people to come.
- Knowing that some women spent as much as two hours every day to do their make-ups, how come there is not a Make-up robot for women ? ( autonomous ). This is all the more interesting that much technology goes into changing the face/shape of women in magazines. How come there isn't a similar technology to evaluate if the make-up is good enough ? Think Snow White mirror.
- People spend an average of 8 hours sleeping yet there is no real good technology to improve sleep. How come there isn't an autonomous pillow that shapes itself around one's head over the course of the sleep. Or since a 32 GB SD card can allow people to record entire sleeping patterns for over 8 hour. What is the software that will allow to check if the pattern is a good one or a detrimental one ?
Friday, August 24, 2007
.. Why, 35 years ago, fly the Atlantic? Why does Rice play Texas? We choose to go to the moon. We choose to go to the moon in this decade and do the other things, not because they are easy, but because they are hard, because that goal will serve to organize and measure the best of our energies and skills, because that challenge is one that we are willing to accept, one we are unwilling to postpone, and one which we intend to win, and the others, too. It is for these reasons that I regard the decision last year to shift our efforts in space from low to high gear as among the most important decisions that will be made during my incumbency in the Office of the Presidency... But if I were to say, my fellow citizens, that we shall send to the moon, 240,000 miles away from the control station in Houston, ... to an unknown celestial body, and then return it safely to earth, reentering the atmosphere at speeds of over 25,000 miles per hour, causing heat about half that of the temperature of the sun--almost as hot as it is here today--and do all this, and do it right, and do it first before this decade is out, then we must be bold."
Do you have any good feel as to why the TV reconstruction of the images featured in this webpage and attendant publications, is still blurry with 40 % of the coefficients specifically for the mug and the soccer ball?My current guesses are as follow:
- the camera is obtaining compressed measurements of a 3-d object but you use a dictionary of 2d functions for the reconstruction ?
- the pseudo-random family used for the projection is not optimally incoherent with the Haar wavelets as opposed to, say, noiselets ?
- exposure time is limited between different mirror configurations ?
1) The optical experiments the Rice team is running right now are probably "low resolution" in the following way. If they took many measurements (say 10s of thousands in order to reconstruct the 4096 pixel image) and then just reconstructed using least-squares (in effect averaging together a bunch of noisy, fully sampled observations) , the final image would still probably be a bit blurry. I don't know if they've tried this; I'll let Kevin and Rich comment.2) I am not sure what values of epsilon they used in the recovery program min TV(x) s.t. ||Ax - y||_2 <= epsilon But if this value was more than something like 1-5% of ||y||_2, the TV recovery would start to get blurry even from "perfect" measurements.
the reason for the blurriness is most likely due to misalignment of the optics; ie: even if we put a regular CCD array where our DMD was located the result would be blurry.your guesses are good ones, but i'm not so sure they could have caused this issue. but we'll keep pondering them.
A “disruptive” technologyDisadvantage in primary marketAdvantage in secondary marketSold in small, low-margin marketEstablished companies concentrate and innovate on primary market; ignore secondaryTimely improvements lessen disruptive technology’s liabilities, increasing markets, market share, margins, etc.A “disruptive” language safe, GC’ed interpretersDisadvantage SLOWAdvantage Rapid Application DevelopSold in small, low-margin market web developers, ISV’s(established competitor ignored market)Established companies concentrate on primary differentiator SPEEDTimely improvements lessen disruptive technology’s liabilities, increasing markets, market share, margins, etc.Moore’s Law (for free!)RAD enhancementsMy criteria: technology mustHave disadvantages: Be mostly ignored by recent PLDI and POPL conferencesAlleviate real problems…"What does it do?"For each candidate technology: 2 slides
- Opportunity what’s the issue?
- Current solutions what’s done now
- Proposal: New disruptive technology
- Disadvantages why some (many?) will scoff
- Unmet needs benefits to adopters
Thursday, August 23, 2007
Please note the shadowing we computed here and a similar occurence below.
The express pallet should have been located next to the astronaut below.
Hayabusa may be coming home thanks to the hard work on Japanese engineers at JAXA. There is now a layer for Gigapixel images in Google Earth. This is going to come handy when we are going to retrieve our camera (Geo-CAM R) from HASP (a High Altitude Balloon to be flown in September) and make large maps like we did last year.
In other news, it also looks like we yawn because we care
Current results suggest that contagious yawning is impaired in ASD, which may relate to their impairment in empathy. It supports the claim that contagious yawning is based on the capacity for empathy.
Wednesday, August 22, 2007
The abstract is pretty self explanatory:
This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements – L1- minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of the Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of the L1-minimization. Our algorithm ROMP reconstructs a sparse signal in a number of iterations linear in the sparsity (in practice even logarithmic), and the reconstruction is exact provided the linear measurements satisfy the Uniform Uncertainty Principle.
A basic code for ROMP can be found on Deenna Needell's page.
The difference between greedy algorithms like ROMP and L1 minimization (which require more cumbersome optimization/ linear programming approach) is touched on in this Q&A at IMA in 2005 by Emmanuel Candes and it all comes down to reducing the sampling needed to obtain good reconstruction.
Thursday, August 16, 2007
Moving forward from the recent Synthesis and L1 entries, I am trying to now review some of the new work on compressed sensing that do not generally fall into the traditional subjects of just compressive sampling.
- Lawrence Carin, Dehong Liu, Wenbin Lin, and Bin Guo, seem to be continuing on their interest in solving the Helmoltz equation with their new preprint: Compressive sensing for multi-static scattering analysis. (Preprint, 2007). It is important because we are beginning to see how their Bayesian Compressive Sensing software helps in solving an integral equation. I am sure I will come back to that paper once I see how it could be used. Right now only inverse problems come to my mind.
- Full Regularization Path for Sparse Principal Component Analysis by Alexandre d'Aspremont, Francis Bach, Laurent El Ghaoui. As far as I could tell the crux of their paper is to use the compressed sensing framework to sparsify the result of a PCA analysis. The generic problem with PCA is that most (few) Principal vectors of interest end up being full (not sparse). Their approach is to use the compressed sensing framework to find the Sparser Principal Components. Note, the code for the DSPCA (Sparse PCA using semidefinite programming) can be found here.
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization by Benjamin Recht, Maryam Fazel, Pablo A. Parrilo This is the most intriguing paper I have seen so far because it promises to make a bridge between compressed sensing and other areas such as operator/matrix compression: Examples include Minimum order linear system realization, Low-Rank Matrix Completion, Low-dimensional Euclidean embedding problems, Image Compression. They make the case that the L1 reconstruction capability in compressed sensing has also been seen in other areas and that compressed sensing is now bringing the theoretical tools as to why these heuristics actually work. The areas of interest include matrices and the issues at hand are not about cardinality of matrices (sparsity) but rather ranks. The Hilbert Space norm that was Euclidian in CS becomes that of Frobenius and the sparsity inducing norm is not L1 but the nuclear norm. The tools to investigate these phenomena in CS are the convex optimization linear programming tools whereas they become that of the semidefinite programming in the context of this article. Lots of interesting and fascinating potential application are listed at the end of the paper. The figure on the right show the same phase change observed in CS but now the x-axis and y-axis represent some measure of the rank of the matrix being tested for recovery. Fascinating. Maybe SeDuMi should be part of the packages for CS from now on? I cannot wait to see how this parallel will play out with Action Respecting Embeddings and Nonlinear Dimension Reduction with Side Information since we were interested in this at some point. But right now it seems it is really a question of skillfully using the Matlab reshape function. As it turns out, CS may indeed have some influence in Machine Learning but in a way I did not anticipate. The Maximum Margin Matrix Factorization algorithm by Jason Rennie and Nathan Srebro may make big headway in enabling the nuclear norm approach developed in this paper. And yes, Pierre, the Netflix prize resolution, in that sense may use some of the concepts in CS. Furthermore, while reconstruction is indeed very interesting and satisfying, I am awaitng what their counterparts in detection will produce ( Richard Baraniuk and Michael Wakin in Random projections of smooth manifolds).
- One of the hot issue in CS is really about how to quantify the amount of sparsity one can get away with when using random or deterministic projections. As we all know Compressed Sensing does not require random projections to work. The bases just need to be incoherent. But when you do use them, what is the least sparse decomposition you can get away with, or how given a random matrix, can one figure out how it can be useful for CS without breaking down. Terry Tao explains what the challenge is here. Anatoly Eydelzon, a doctoral candidate at Rice will present his thesis on the subject on August 30th ( Deterministic Conditions for Solution Recovery in Compressive Sensing and Error Correction)
- Another way to go about this is to solve this issue with a deterministic algorithm. This is what Mark Iwen is doing with his paper: A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods. First, it is nice to see another CS paper that specifically refers to group testing in the form of the Chinese Remainder Theorem. Mark Iwen modifies an algorithm develop by Graham Cormode and Muthu Muthukrishnan. One of the interesting thing about new papers is how Compressed Sensing is defined, which is always a little bit different than before. For instance, he gives a very compact definition of CS that I cannot recall being so clearly expressed before.
The general CS setup is as follows: Let A be an N-length signal/vector with complex valued entries and be a full rank N × N change of basis matrix. Furthermore, suppose that T A is sparse (i.e., only k ≪ N entries of T A are significant/large in magnitude). CS methods deal with generating a K ×N measurement matrix,M, with the smallest number of rows possible (i.e., K minimized) so that the k significant entries of · A can be well approximated by the K-element vector result of M· T A. (1) Note that CS is inherently algorithmic since a procedure for recovering T A’s largest k-entries from the result of Equation 1 must be specified.At the end of the paper, it also becoming clear as to how CS is going to affect linear algebra:
Compressed Sensing (CS) methods provide algorithms for approximating the result of any large matrix multiplication as long as it is known in advance that the result will be sparse/compressible.This is very reminiscent of the Fast Multipole method that initially was thought as a mere improvement to some electrostatic or gravitational computations but eventually yielded major advances in many other areas. Mark used the approach of Cormode and Muthukrishnan ( Combinatorial algorithms for compressed sensing. G. Cormode and S. Muthukrishnan. SIROCCO 2006. DIMACS TR 2005-25)
- Michael Lustig has released a new version of SparseMRI a collection of Matlab functions that implement the algorithms and examples described in the paper M. Lustig, D.L Donoho and J.M Pauly "Sparse MRI: The Application of Compressed Sensing for Rapid MR Imaging ". A review and introduction on the subject for non-specialists can be found here.
- I could not review this paper by Ashwin Wagadarikar, Renu John, Rebecca Willett, and David Brady. "Single disperser design for compressive, single-snapshot spectral imaging," SPIE Optics and Photonics, 2007. [http://www.ee.duke.edu/
~willett/papers/WagadarikarSPI] because the pdf file seems to be bad. E2007.pdf
- On a very local note, Ron DeVore will give a course on Compressed Sensing at Texas A&M University in the Math department this fall: Math 689 Section 602, in Blocker, http://www.math.tamu.edu
- If you know of a specific class or presentation made on the subject of Compressed Sensing and related areas please send me an e-mail, I'll try to make to map those and make it available.
- [Update: August 20. Muthu Muthukrishnan pointed to a variant of the JL transform by Jiri Matousek (here ). Does this new transformation follow the RIP ?]
Tuesday, August 14, 2007
Damaris has a small entry on her work currently looking at the Shuttle damaged tiles. We had a similar project at STC where we would look at the belly of the shuttle using an HD camera at 60 frames per second and eventually provide 3D photogrammetry of the belly of the Orbiter from several hundred meters down.
One of the thesis of the subject was done by Paul Gersting at Texas A&M University under Johnny Hurtado and Mark Lemmon and was entitled: A photogrammetric on-orbit inspection for orbiter thermal protection system. When the shuttle would perform the RPM (Rendez-Vous Pitch Maneuver or shuttle back flip) below the International Space Station, our HEOCam system would have been able to evaluate impact depth as Paul shows in his work.
The IPAM/UCLA Graduate Summer School on Probabilistic Models of Cognition: The Mathematics of Mind has finished. The presentations and webcasts can be found here.
Saturday, August 11, 2007
As hinted on previously and on John Wiseman's blog, we are not semi-finalist to the urban Challenge. We did not make that bridge. Thank you for all the good wishers. At some time, we'll try to write and talk more about our system of ominidirectional cameras using compressed sensing and dimensionality reduction in policies we intended to accomplish during the site visit but did not have time to do.
In the meantime, our payload on HASP was integrated, we are looking forward to a second-flight of GeoCam and a new flight of Hyper-GeoCam, an Hyperspectral Random Lens Imager (following the foodsteps of the MIT Random Lens Imaging system by Rob Fergus, Antonio Torralba, William Freeman.)