SPOQ: norm ratio sparsity restoration (how I discovered sparsity and stopped worrying about it)

[TL;DR] How I discovered sparsity and stopped worrying about it

This is a journey into sparsity. The story started in 2009, in the South of France, and the nice island of Porquerolles. Here, clear blue water.

France, Porquerolles, plage Notre-Dame

 

 

 

 

 

There was a workshop organized in June called Porquerolles 2019: Approximation and optimization in image restoration and reconstruction. A bunch of first class researchers were there: 

Amel Benazza-Benyahia, Jérôme Bolte, Antonin Chambolle, Caroline Chaux, Philippe Ciuciu, Albert Cohen, Patrick Louis Combettes, Claude Comtat, Christine de Mol, Alvaro R. De Pierro, Michel Defrise, Ron DeVore, Jalal Fadili, Mario Figueiredo, Massimo Fornasier, Jacques Froment, Yves Goussard, Gabor Herman, Jérome Idier, Dirk Lorenz, Russell Luke, Francois Malgouyres, Pierre Maréchal, Ali Mohammad-Djafari, Stanley Osher, Valérie Perrier, Jean-Christophe Pesquet, Gabriel Peyré, Aleksandra Pizurica, Andrew Reader, Elena Resmerita, Marc Sigelle, Gabriele Steidl, Marc Teboulle, Joel Trussell, Michael Unser, Dimitri Van de Ville, Isao Yamada

The program was wonderful. The trade-off between sea, science and sun was so easy. At that time, I had been working mostly with signals and images, processing them with sparsity-promoting decompositions: complex orthogonal/biorthogonal dual-tree wavelets with interesting covariance properties able at multichannel/multicomponent image denoising, tighly oversampled complex filter banks. We wanted to have data become sparser through a projection on some vector basis, union of bases or frames. Yet, what sparsity really meant was not fully clear to me. The count measure $\ell_0$ of course, but it is not practically usable for several reasons. 



[TO BE CONTINUED, THEN MATERIALS]

So: SPOQ means, in Swedish, "Svenskt Pediatriskt Ortopediskt Qvalitetsregister" (Swedish Pediatric Orthopaedic Quality register). 

And Mr SPOQ (at BandCamp, and...) is a german electronic music artist (from Aschaffenburg, Germany) as well. In his Cinnamon album, there is a tune called "Distance" (at BandCamp). And mathematically speaking, norms and distances are somewhat related.

But how does all the above relate to our SPOQ (SPOQ Lp-Over-Lq Regularization for Sparse Signal Recovery applied to Mass Spectrometry) algorithm? Later, it is way too late. 

L0 sparsity count index, L1-norm non-smooth convex proxy, L1/L2-norm ratio and Lp/Lq quasinorm/norm ratio smooth non-convex penalties.

Abstract: Underdetermined or ill-posed inverse problems require additional information for sound solutions with tractable optimization algorithms. Sparsity yields consequent heuristics to that matter, with numerous applications in signal restoration, image recovery, or machine learning. Since the 

ℓ0

 count measure is barely tractable, many statistical or learning approaches have invested in computable proxies, such as the ℓ1

 norm. However, the latter does not exhibit the desirable property of scale invariance for sparse data. Generalizing the SOOT Euclidean/Taxicab ℓ1

/

ℓ2

 norm-ratio initially introduced for blind deconvolution, we propose SPOQ, a family of smoothed scale-invariant penalty functions. It consists of a Lipschitz-differentiable surrogate for ℓp

-over-ℓ

q

 quasi-norm/norm ratios with p∈]0,2[

 and q≥2

. This surrogate is embedded into a novel majorize-minimize trust-region approach, generalizing the variable metric forward-backward algorithm. For naturally sparse mass-spectrometry signals, we show that SPOQ significantly outperforms ℓ0

, ℓ1

, Cauchy, Welsch, and \celo penalties on several performance measures. Guidelines on SPOQ hyperparameters tuning are also provided, suggesting simple data-driven choices.