Showing posts from April, 2008

Flat Noise Set - on Fast Noiselet transform

After first try to provide some code for the noiselet transform matrix, which yields a flat noise set of coefficients from the Haar system (and to obtain nice pictures), a valuable implemetation has been made public. No lie, fastestMatlab code for noiselets is now available from Laurent Jacques (direct link). David Donoho(*) recently recalled that the compressed sensing litterature shared similarities with concepts in other fiels (an oft essential remark). For instance in data stream processing, as for “heavy hitters” or “Iceberg queries”. The Fast Noiselet is not the nastiest floe in this ocean of litterature.

(*) David L. Donoho, Compressed Sensing, IEEE Transactions on Information Theory, April 2006 (pdf copy).

On complex hadamard matrices

Connections or connexions?

François Morellet is a painter, scultor, engraver, who turned abstract by the 1950's. Some of his works carry strange connections with sparsity, wavelets and even compressive sensing. First, his name, akin to both a crocodile and Jean Morlet, who died almost one year ago. Then, he authored a work entitled "4 trames de tirets simples (non quinconce) 0°-45°-90°-135°", which obviously refer to a set of four oriented separable ("non quincunx") frames, very similar to complex dual-tree wavelets. The remaining terms "tirets simples" (simple dashes) may refer to Haar or Hadamard like vectors. Less structured grids (see Any grid) are also present, as in this "Répartition aléatoire de 40 000 carrés":

The following "3 doubles trames 0°, 30°, 60°" is far better structured. Connections. Or Connexions (, at Rice University, providing Content Commons of free, open-licensed educational materials in fields such as music, electrical engi…

RIP scene sends Smog (Noiselet today)

Recently, Processing Vein Mess was proposed as an applicative anagram for Compressive sensing. Its Compressed sensing avatar possesses a much nicer anagram: "RIP scene sends Smog". This was illustrated in a recent talk by Albert Cohen around the Restricted Isometry Property (RIP). For practical applications, Compressive sensingonset lies in the developpement of specific observation matrices. Noiselets are an example of those. Let us quote artist Michael Thieke about them:
Very sparse. Very minimal.
These musicians with their instruments make sounds that may not have been intended by the original inventors. They do this in a way that at first seems to be a very random. After a longer listen, the inspirations soak through. These “noiselets and sounduals” (my words entirely) may be improvised, but they are very potent in their expressive capability.
Real, or imaginery (for noiselet Matlab code)?

RIP, not RIP - a little bit on compressed sensing

Shall the Restricted Isometry Property (RIP) Rest In Peace (RIP again)?

This afternoon, Albert Cohen presented recent findings (made with Wolfgang Dahmen and Ronald DeVore) on Compressed sensing and best k-term approximation. These findings pertain to the fields of compressive sensing (CS, see Nuit Blanche for some live coverage) and non-linear approximation (NLA), namely: how do fixed linear measurements (CS) and adaptive linear measurements (NLA) compare for signal approximation in the lp norm? Both in a deterministic and a probabilistic fashion. A. Cohen nicely reviewed some references on the topic, including the interesting FRI (Finite Rate of Innovation) by Per Luigi Dragotti and Martin Vetterli (et al.), nicely covered here (we come back later on this approach) and the compressive sensing resources. He emphasized an approach based on decoupling (1) the information quantity and (2) the algorithms. The basic question is: given some unknown x, presumably sparse, linearly observed…