Trainlets: cropped wavelet decomposition for high-dimensional learning

It's being a lonng time: element 120 from the aperiodic table of wavelets is the trainlet, from Jeremias Sulam, Student Member, Boaz Ophir, Michael Zibulevsky, and Michael Elad, Trainlets: Dictionary Learning in High Dimensions:

Abstract: Sparse representations has shown to be a very powerful model for real world signals, and has enabled the development of applications with notable performance. Combined with the ability to learn a dictionary from signal examples, sparsity-inspired algorithms are often achieving state-of-the-art results in a wide variety of tasks. Yet, these methods have traditionally been restricted to small dimensions mainly due to the computational constraints that the dictionary learning problem entails. In the context of image processing, this implies handling small image patches. In this work we show how to efficiently handle bigger dimensions and go beyond the small patches in sparsity-based signal and image processing methods. We build our approach based on a new cropped wavelet decomposition, which enables a multi-scale analysis with virtually no border effects. We then employ this as the base dictionary within a double sparsity model to enable the training of adaptive dictionaries. To cope with the increase of training data, while at the same time improving the training performance, we present an Online Sparse Dictionary Learning (OSDL) algorithm to train this model effectively, enabling it to handle millions of examples. This work shows that dictionary learning can be up-scaled to tackle a new level of signal dimensions, obtaining large adaptable atoms that we call trainlets.

They offer a base dictionary used within a double sparsity model to enable the training of adaptive dictionaries. The associated package is here, from Michael Elad software page.  The  cropped wavelet decomposition enables a multi-scale analysis with virtually no border effects. An entry  to trainlets has added to WITS, the aperiodic table of wavelets.

But things always ends up with a song! Two of my favorite train songs, by  Porcupine tree (Trains) and the Nits (The train).

Beaujolais nouveau: anagrams and Cambridge University research

According to a researcher (hic) at Salonic  University, it doesn't matter in what order the letters in a word are, the only important thing is the quantity of Beaujolais Nouveau wine you have drunk before. This external advertising panel outside a Nicolas shop distills: "Le Beaujolais nouveau est arrivé" in a drunkard anagram: "Le beuajolias nuovaeu est avriré". See what it does to the poor Alan Parsons Project.

The ad takes on the September 2003 hoax on the unimportance of the order of letters, according to a forged  researcher (sic) at Cambridge University (Aoccdrnig to a rscheearch at Cmabrigde Uinervtisy).

Even if not completely invalid, the hoax may be checked with Switcharoo! (Order of letters in a word doesn't matter? The hell it ...). For instance, it kinda works on Wim Sweldens' definition of the wavelet in the introduction for his PhD thesis, Construction and Application of Wavelets in Numerical Analysis, in 1994 (see the scrambled WITS: Where is the Starlet?)

Original: Uit de wiskundige analyse volgde dat de integraal van deze functie nul moet zijn en dat deze functie naar nul moet convergeren als het argument naar oneindig gaat. M.a.w. deze functie moet een beetje "schommelen" en dan geleidelijk uitsterven; het is een soort "lokaal golfje".

Scrambled: Uit de wskngdiuie aaslyne vdogle dat de igtanaerl van deze ficntue nul meot zijn en dat deze ficntue naar nul meot ceervongern als het agnumert naar oineindg gaat. M.a.w. deze ficntue meot een bteeje "seoemmhcln" en dan gileeeiljdk uirsteevtn; het is een sroot "lakaol gfojle".

It works with Dutch. I cannot equally read both texts. Here are two interesting texts, with studies in different languages, pertaining to the case. None from Cambridge university.

Carol Whitney. How the brain encodes the order of letters in a printed word: the SERIOL model and selective literature review. Psychon Bull Rev. 2001 Jun. 8(2):221-43, and associated publications.

This paper describes a novel theoretical framework of how the position of a letter within a string is encoded, the SERIOL model (sequential encoding regulated by inputs to oscillations within letter units). Letter order is represented by a temporal activation pattern across letter units, as is consistent with current theories of information coding based on the precise timing of neural spikes. The framework specifies how this pattern is invoked via an activation gradient that interacts with subthreshold oscillations and how it is decoded via contextual units that activate word units. Using mathematical modeling, this theoretical framework is shown to account for the experimental data from a wide variety of string-processing studies, including hemispheric asymmetries, the optimal viewing position, and positional priming effects.

Jonathan Grainger and Thomas Hannagan. Explaining word recognition, reading, the universe, and beyond: A modest proposal. Behavioral and Brain Sciences, August 2012.

In the last decade, reading research has seen a paradigmatic shift. A new wave of computational models of orthographic processing  that  offer  various  forms  of  noisy  position  or  context-sensitive  coding  have  revolutionized  the  field  of  visual  word recognition. The influx of such models stems mainly from consistent ?ndings, coming mostly from European languages, regarding an apparent insensitivity of skilled readers to letter order. Underlying the current revolution is the theoretical assumption that the insensitivity of readers to letter order reflects the special way in which the human brain encodes the position of letters in printed words. The present article discusses the theoretical shortcomings and misconceptions of this approach to visual word recognition. A systematic  review  of  data  obtained  from  a  variety  of  languages  demonstrates  that  letter-order  insensitivity  is  neither  a  general property of the cognitive system nor a property of the brain in encoding letters. Rather, it is a variant and idiosyncratic characteristic of some languages, mostly European, reflecting a strategy of optimizing encoding resources, given the specific structure of words. Since the main goal of reading research is to develop theories that describe the fundamental and invariant phenomena of reading across orthographies, an alternative approach to model visual word recognition is offered. The dimensions of a possible universal model of reading, which outlines the common cognitive operations involved in orthographic processing in all writing systems, are discussed.

Do not "Drunk in the gutter", "Greet unkind truth".

Hyperbolets (on WITS: Where is the Starlet)

A new conference is born: UCCV 2013, The 1st IEEE Workshop on User-Centred Computer Vision, due in Florida, Tampa. on January 2013. It has been added to SIVA Conferences.

While the shearlets are enjoying some spread (cf. Shearlets from MIA 2012 or this paper), some of their contributors are involved in hyperbolets, or hyperbolic wavelets, closely related cousins. Here they are (as on WITS: where is the Starlet):

Hyperbolets

In short:	An example of multi-composite wavelets with hyperbolic scaling law
Etymology:	From the hyperbola (wiki entry), with a potential reference (article no available on 2011/05/26) to the parabolic scaling law of the shearlets
Origin:	Glenn R. Easley, Demetrio Labate, Vishal M. Patel: Multi-composite wavelet estimation, Proceedings of SPIE Volume 8138, Wavelets and Sparsity XIV, Aug. 2011 (local copy) Abstract: In this work, we present a new approach to image denoising by using a general representation known as wavelets with composite dilations. These representations allow for waveforms to be defined not only at various scales and locations but also at various orientations. For this talk, we present many new representations such as hyperbolets and propose combining multiple estimates from various representations to form a unique denoised image. In particular, we can take advantage of different representations to sparsely represent important features such as edges and texture independently and then use these estimates to derive an improved estimate. The hyperbolet construction is further refined in: G. R. Easley, D. Labate and V. M. Patel, Hyperbolic shearlets, IEEE International Conference on Image Processing (ICIP), Orlando, FL, 2012, submitted (local copy) G. R. Easley, D. Labate, and V. M. Patel, Directional multiscale processing of images using wavelets with composite dilations, submitted 2011 (local copy)
Contributors:	Glenn R. Easley (no personal page), Demetrio Labate, Vishal M. Patel
Some properties:	Tiling of the frequency domain associated with an hyperbolic system of wavelets with composite dilations. Closely related to shearlets
Anecdote:
Usage:
See also:	The above work might be related to Glenn R. Easley, Demetrio Labate: Critically Sampled Wavelets with Composite Dilations (local copy), preprint, 2011, which develops interesting critically sampled directional wavelet schemes (DWTShear, CShear, QDWTShear)
Comments:

More on the topic:
2D wavelets: A panorama on multiscale geometric representations, intertwining spatial, directional and frequency selectivity

WITS: Shearlets from MIA 2012

At the wonderful MIA 2012 (hey Gabriel, did i tell you how that was great?), two talks have been devoted to shearlets (Gitta Kutyniok, Gabriele Steidl), yet another geometric multiscale representation for images. And a brand new Matlab toolbox from Gabriele Steidl group named FFST (fast finite shearlet transform) and developed by Sören Haüser has been announced.

Shearlet-Zerlegung eines Auges.© Gitta Kutyniok

A good opportunity to update a little corner of WITS: Where is the Starlet, which was beginning to grow a few webs. Mmh, look like some familiar frequency domain partitioning... And now for something completely different: number 1, the shearlet... the shearlet! (Monty Python inside)




Shearlets

In short:	Non-separable wavelets built out of parabolic scaling, shear, and translation operations
Etymology:	From shear, a sheer distorsion
Origin:	Labate, Demetrio and Lim, W-Q. and Kutyniok, Gitta and Weiss Guido, Sparse multidimensional representation using shearlets (local copy) A handful lot of papers is available here: shearlet papers. A first overview is given in Shearlets. The First Five Year (Oberwolfach Report, 2010, local copy).
Some properties:	Unlike curvelets, shearlets form an affine system with a single generating mother shearlet function parameterized by a scaling, a shear, and a translation parameter. Provides the same approximation properties as curvelets, albeit with a different directional sensitivity. Exist in band-limited or compact support flavors. Possess natural, canonical smoothness spaces, called shearlet coorbit spaces, similar to Besov spaces for wavelets. Apparently extend to arbitrary any dimensions.
Usage:	Image denoising, restoration, morphological component analysis
See also:	The shearlet website, recently updated with ShearLab (... a rationally designed digital shearlet transform) For discrete implementation, there exists for instance a Digital Shearlet Transforms or Development of a Digital Shearlet Transform Based on Pseudo-Polar FFT. Shearlet Matlab toolboxes are available at ShearLab matlab toolboxes, local shearlet toolbox by G. Easley and FSST: ShearLab-1.1 (Implementation based on Cartesian Grids) (direct link) ShearLab-PPFT-1.0 (Implementation based on Pseudo-Polar Grids) (direct link) The recent (2012) FFST - Fast Finite Shearlet Transform by Sören Häuser The FFST package provides a fast implementation of the Finite Shearlet Transform. Following the the path via the continuous shearlet transform, its counterpart on cones and finally its discretization on the full grid we obtain the translation invariant discrete shearlet transform. Our discrete shearlet transform can be efficiently computed by the fast Fourier transform (FFT). The discrete shearlets constitute a Parseval frame of the finite Euclidean space such that the inversion of the shearlet transform can be simply done by applying the adjoint transform. with a Fast Finite Shearlet Transform tutorial (local copy)
Comments:	Potential a hard competitor, for years to come, to the quite oversold curvelets (IMHOlet: In My (little) Humble Opinion)

More on the topic:
2D wavelets: A panorama on multiscale geometric representations, intertwining spatial, directional and frequency selectivity

WITS: Tetrolet wavelets

The WITS (and the Virtue) honors today tetrolets, a breed of Haar-type wavelet transform based on tetrominoes. The preprint: "Tetrolet Transform: A New Adaptive Haar Wavelet Algorithm for Sparse Image Representation", may be found at J. Krommweh page (or local copy). The abstract reads:

In order to get an efficient image representation we introduce a new adaptive Haar wavelet transform, called Tetrolet Transform. Tetrolets are Haar-type wavelets whose supports are tetrominoes which are shapes made by connecting four equal-sized squares. The corresponding filter bank algorithm is simple but enormously effective. In every level of the filter bank algorithm we divide the low-pass image into 4 × 4 blocks. Then in each block we determine a local tetrolet basis which is adapted to the image geometry in this block. An analysis of the adaptivity costs leads to modified versions of our method. Numerical results show the strong efficiency of the tetrolet transform for image compression

WITS: Steerlet wavelets

Let us welcome the steerlets, a new breed we have little information about so far, except it is featured at SPIE Wavelet XIII: Papadakis, Azencott and Bodmann at Univ. Houston: Three dimensional steerlets: a novel tool for extractiong textural and structural features in 3D images, SPIE Wavelet XIII, August 2009. Those guys from Texas do love longhorns. And don't forget the WAIP 2010 (Wavelet Applications in Industrial Processing) conference CfP deadline on June 22nd.

WITS: MIMOlet wavelets

There might be a feeling of complexity in the burgeoning world of wavelets. A relatively general multiresolution framework, entitled MIMOlet (mee-moh-let), has been proposed by Guillaume Flanders et al, with a french-dutch-belgian team originating form Lille university. This scheme includes most of the known forms of discrete filter banks, critical or overcomplete, separable or directional. It borrows its name from MIMO (multi-input, multi-output) systems. More details to be found at this page (broken link at the time of writing). Its extension to the sphere (Booldelill et al.) is in progress, as a generalization to needlets (see for instance here).

WITS: Bathlet wavelets

The WITS (and the Virtue) honors today bathlets, a breed of wavelets based on a balanced weighted uncertainty approach. Colorado 7-eleven (7-11 math problem here) stores fear a Klingon-weaponed robber threatening clerks with a spiky, crescent shaped Star Trek inspired sword called bat'leth or Klingon's personal sword of honor. Since this description is only a coarse approximation, more details are to be found at The Denver Channel.

In the wavelet world, bathlets originate from the University of Bath, wavelets have been designed based on an Heisenberg uncertainty based metric balancing both their time and frequency spread. The Bath Wavelet warehouse serves both orthogonal and biorthogonal wavelet coefficients

A handfull of Bat'leth

Further reading on bathlets:
"Orthonormal wavelets with balanced uncertainty", DM Monro, BE Bassil and GJ Dickson, IEEE International Conference on Image Processing, 1996, Vol.2, pp.581-584 (local copy).
"Space-frequency balance in biorthogonal wavelets", DM Monro and BG Sherlock, IEEE International Conference on Image Processing, 1997, Vol.1, pp.624-627 (local copy).

Bat'leths: Sizing Your Bat'leth (for Vulcans or Klingons only)

Major en *let - In honor of Jean Morlet

Jean Morlet (or the Major en -let, in french in the text), one of the fathers of all wavelets, along with some precursors, as in the nice notice Precursors in mathematics: early wavelet bases, by Hans G. Feichtinger, is honored at the end of October in Marseille, France.

A preliminary program below the Morelet crocodile:
October 27 - 29th, 2008
Continuous wavelet transform and Morlet's wavelet, 1978-2008 : International colloquium in honor of Jean Morlet
Organizer: G. Saracco (CNRS, CEREGE Aix-en-Provence)

Centre International de Rencontres Mathematiques (CIRM), Campus de Luminy, Marseille, France

*Preliminary Program*:

1-Alex Grossmann: «Continuous wavelet theory and Morlet's wavelet» (Hommage à J. Morlet) , (CNRS-Evry)

2-Y. Meyer, membre de l'Académie des Sciences: «Des ondelettes continues en géophysique
aux bases orthogonales d'ondelettes» (hommage a J. Morlet) (ENS-Cahan)

3- Pierre Goupillaud : PR, Two superb mathematicians who's innovations were the product of asking question that others had overlooked. (Hommage à J. Morlet), (SEG., USA)

5-Patrick Flandrin, DR: Wavelets, surrogates and non-stationarities,(ENS-Lyon)

6-Stephane Jaffard, PR: Directional continuous wavelet transforms and application to directional smoothness of functions (Paris XII)

7-Ronald Coifman, PR: Wavelet and diffusion geometries on seismic data sets (Yale Univ., USA)

8-Alain Arneodo, DR: Surfing on the genome: a tribute to J. Morlet (ENS-Lyon)

9-Jean-Pierre Antoine: The wavelet transform on the sphere: continuous vs. discrete (Louvain, Belgique)

10-Jean-Luc Stark, : Compressed sensing in astronomy (CEA-Paris)

11-Nick Kinsbury: Complex-valued wavelets, the dual tree and the Hilbert Transform: Why these lead to
approximate shift invariance? (Cambridge Univ., GB)

12-Thierry Paul, DR: Non linear continuous wavelets and non linear coherent states (ENS-Cachan)

13-Ginette Saracco: Multi-scale tomography of buried magnetic or electrical sources: Its localization and characterization.
Application to archaeological structures or volcanic system (CNRS-CEREGE, Aix en provence)

14-Gregory Beylkin, PR: On approximation by Gaussian and its applications (Boulder Univ. Co, USA)

15-Marie Farge, DR: Continuous wavelet analysis of vortex bursting in turbulent flows (ENS-Paris)

16-Matthias Holschneider, PR, Directionnal Poisson wavelets on the sphere (Potsdam, Allemagne)

17- Jean-Claude Risset, DR emerite, medaille d'Or du CNRS, Morlet wavelet are good to hear (CNRS-LMA, Marseille)

18- Peter Frick, PR, Double Wavelet analysis: Method for recognizing stellar activity peculiarities (Moscou Russie)

19- Pascal Sailhac, From seismic wavelets to wavelet transform: using Berlage wavelets to the detection
and characterization of damped transient waves occurring in geophysical time-series", (IPG-Strasbourg)

20- Nicolas Thouveny, PR, Extraction of frequency modulation laws from Earth's magnetic field intensity records
by complex continuous wavelet analysis; contribution to understanding the geodynamo behavior. (CEREGE, Univ Aix-Marseille, Aix en Provence)

21- Say Song Goh, PR, Uncertainty Principles for the Continuous Wavelet Transform, (Rep Singapore)

22- Maurizio Fedi, Discrete and Continuous Wavelet Transform of potential fields with different choices of analyzing wavelets, (Naples Univ., Italie)

23- Roddam Narasimha, PR, Morlet Wavelets and the Solar Connection with Indian Monsoon Rainfall, (Bingalore, Inde)

24- Albert Cohen, PR, Adaptive multiresolution analysis based on anisotropic triangulations, (Univ. Pierre & Marie Curie, Paris)

25- Agissilaos Athanassoulis, Strengthening semiclassical approximations with the use of coarse-scale representations, (ENS-Ulm, Paris)

26- Nele de Shepper, Multi-dimensional continuous wavelet transforms and General Fourier transforms in Clifford Analysis, (Ghent Univ, Belgium)

Featured on the SIVA conferences web page.