Sunday, September 20, 2009

CS:SPAMS, SPArse Modeling Software, a dictionary building facility and more...

Following up on friday's entry on Dictionary learning and as promised a month and a half ago on this blog, Julien Mairal, Francis Bach, Jean Ponce and Guillermo Sapiro came through with the release of SPArse Modeling Software or SPAMS (yes, I know, this message is going to do very well with spam filters ) which as you recall seems to be very promising in the rapid construction of dictionaries. From the introduction:
SPAMS (SPArse Modeling Software) is an optimization toolbox. It is composed of a set of binaries implementing algorithms to address various machine learning and signal processing problems involving a large number of small/medium size sparse decompositions. Examples of such problems are presented in [14, 13].

The library is coded in C++, is compatible with Linux 64bits and 32bits Operating Systems and Mac OS, and is interfaced with Matlab. Other OS/architectures (Windows) or environments (R, Python, …) will eventually be included in future releases. It exploits multi-core CPUs when available.

Version 1.0 of the toolbox includes

  • The online dictionary learning technique of [14, 13] and its variants for various matrix factorization problems.
  • Orthogonal Matching Pursuit, also known as Forward Selection [22, 19]. The implementation is based on a Cholesky-decomposition and optimized for solving in parallel a large number of decomposition problems.
  • The LARS algorithm [6]. The implementation is also Cholesky-based and optimized for solving in parallel a large number of decomposition problems.
  • A weighted version of LARS.
  • A coordinate-descent approach for ℓ1-decomposition problems [8, 7, 23], also optimized for solving in parallel a large number of problems.
  • A first-order proximal method as described in [21] and its accelerated version for solving, Lasso, Elastic-Net and Fused Lasso problems.
  • A homotopy method for the Fused-Lasso Signal Approximation as defined in [7] with the homotopy method proposed in [13].
  • A tool for projecting efficiently onto a few convex sets inducing sparsity such as the ℓ1-ball using the method of [12, 5], and Elastic-Net or Fused Lasso constraint sets as proposed in [13].
  • A few tools for performing linear algebra operations such as a conjugate gradient algorithm.
The number of functions is intended to grow. Especially, the authors would like to include in future major releases image processing tools corresponding to the paper [16] and classification tools such as the ones from [15, 18, 17].

SPAMS uses at the moment a proprietary license, but its usage is free for non-profit research or test purposes. For other usage, please contact the authors (see license for more details).

The software uses function call to BLAS/LAPACK functions [4, 3, 10, 1]. It can use either the Intel Math Kernel Library (run-time files are included in the software package) or the free implementation ATLAS (files are included as well in the software package).

The toolbox is written by Julien Mairal (INRIA), with the collaboration of Francis Bach (INRIA), Jean Ponce (Ecole Normale Supérieure) and Guillermo Sapiro (University of Minnesota).

Julien tells me that a Windows version might be available in the future. Windows users are people too! It would be a shame if this capability were to follow the example of the Linux only curvelet transform. Anyway, this software is evidently linked from the dictionary section of the Big Picture in Compressive Sensing page.

Image Credit: NASA/JPL/Space Science Institute, Saturn's ring on September 13th, 2009

No comments: