Introduction to k-LiMapS

Analogously to the well known greedy strategy called Orthogonal Matching Pursuit (OMP), k-LiMapS is a new algorithm to solve the sparse approximation problem over redundant dictionaries where the input signal is restricted to be a linear combination of at most k atoms of a fixed dictionary. The basic strategy of the method rests on a family of nonlinear mappings which results to be contractive in a interval close to zero. By iterating contractions and projections the method is able to extract the most significant components also for noisy signal which subsumes an ideal underlying signal having sufficiently sparse representation. For reasonable error level, the fixed point solution of such iterative schema provides a sparse approximation containing only the nonzero terms characterizing the unique sparsest representation of the ideal noiseless sparse signal. The heuristic method so derived has been applied both to synthetic and real data generated by combining exact signals drawn by usual Bernoulli-Gaussian model and Gaussian noise. The figure depicts both the k-LiMapS and OMP mean square errors over the data.

Performances

Each point on the grid shows the cumulative mean square error (MSE) between the original and reconstructed signals. The grid of $\delta\times\rho$ values is done with $\delta$ ranging in the interval [.01, 5] and $\rho$ ranging in [.01, 1], where $\rho=k/n$, $\delta=n/m$ and $n\times m$ represents the dictionary size.


The annealing-like behavior exhibited by klimaps hitting the non required coefficients already at the beginning of the first iterations (15 and 30) for a 10-sparse signal, as shown in the following plotting:

ECG Performances

klimaps_slides (slide presentation at ISPITT '11)


Matlab code

The MATLAB code of k-LiMapS and related resources are available under GPL.

klimaps-v1.0.tgz (tarball with MATLAB code, tests and examples)


Face Recognition

Holistic

The entire process for face recognition, namely the klimaps_holistic_FR system, is summarized in the flow diagram in Figure and consists in the following steps:

  1. Projection: embeds both training and test images in the LDA space in order to extract holistic facial features
  2. Sparsity: gives a sparse representation of a test image by applying klimaps and using the dictionary in the LDA space
  3. Classification: finds the identity by a discriminant rule based on minimum residue

diagram

Matlab code

Here is an archive containing the MATLAB code for the holistic face recognition system based on klimaps together with the known algorithms SRC, CRC and Lasso, used for the same recognition task. To test the algorithms some of the most common face datasets are provided. The code of klimaps_holistic_FRS and related resources are available under GPL.

klimaps_holistic_FRS

Face_Datasets


ECG Compression

The algorithm for ECG signal compression and reconstruction based on klimaps algorithm is summarized in the flow diagram depicted below. It consists in a block-wise sparse coding preceded by standard preprocessing and dictionary creation, and followed by a final lossless compression of sparse coefficients.


ECG Performances


In the next figure it is depicted an example of compressed signal extracted from the record 100 of MIT-BITH dataset, on which we reach an impressive compression level. From the top, we illustrate the original signal without baseline, the reconstructed signal, and the error signal. Note that the sample errors are equally distributed over all regions of the cardiac signal, hence giving more worth to the proposed strategy.

ECG Performances

Compression of the record 100 with $CR = 75.12$ and $PRD = 0.68$. (a) Original signal. (b) Reconstructed signal. (c) Error signal.


Matlab code

Here is an archive containing the MATLAB code for the ECG compression method based on klimaps and some ECG signals of MIT-BITH database. The code for ECG compression and related resources are available under GPL.

ECG_compression

MITDB_signals


References

A. Adamo, G. Grossi and R. Lanzarotti

Sparse Representation based Classification for Face Recognition by k-LiMapS Algorithm

ICISP, 2012

A. Adamo, G. Grossi and R. Lanzarotti

Local features and Sparse Representation for Face Recognition with Partial Occlusions

ICIP, 2013

A. Adamo, G. Grossi and R. Lanzarotti

Face Recognition in Uncontrolled Conditions Using Sparse Representation and Local Features

ICIAP, 2013