March 22, 2020

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 q2
. 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.





Chants des confins : compilation on COVID-19/coronavirus occasion


Chants des confins (Confines' songs) is one music for each (relaive) day of confinement due to the COVID-19 coronavirus pandemia. And two lines. Two rhymes. Rarely more. I listened to each song five times in a row before posting it. 

So far:  Frankie Goes To Hollywood, Pink Floyd, Télépopmusik,, Henry Purcell (by Sarah Connolly  and Marianne Beate Kielland), Villagers of Ioannina City, Philip Glass with Lavinia Meijer (harp), Dave Brubeck & Paul Desmond (a kind of fake on Take five) (and the Stranglers), Mano Negra, Loney Dear, Sarah Vaughan, Deep Purple (and Navarone), The Kyteman Orchestra (Colin Benders), Dominique A (et Alain Bashung), VALD, George Frideric Handel (sung by Nathalie Stutzmann & Philippe Jaroussky), Kings of convenience and Feist, Les Têtes Raides, Yom (Guillaume Humery) and the wonder rabbis, Sting (interpreted by Pat Metheny, Nils Landgren, Esbjörn Svensson, Michael Brecker, Lars Danielsson, Wolfgang Haffner), Andrea da Florentia (Ensemble Syntagma), Ilene Barnes, Marillion, Opeth, Meute (Brass techno band on Disclosure and Eliza Doolittle and a Flume Remix, Osiris, Porcupine Tree (Steven Wilson), The Stranglers (and Mariachi Mexteca feat. Hugh Cornwell), Suzanne Vega, The Nits, The Supremes, Nena, Gov't Mule, Dire Straits, Microfilm, Sylvain Chauveau, Wolves in the Throne Room, Genesis (Peter Gabriel), Barclay James Harvest, Nancy Sinatra & Lee Hazlewood, Loudblast, Archive, Calvin Russell, Laibach (The Beatles), Giovanni Battista Pergolesi (Gérard Lesne, Il seminario musicale), Yaron Herman (and Radiohead again, yes), Samaris, Bel Canto (with the beautiful voice of Anneli Drecker), Sinéad O'Connor (and The Chieftains), Youn Sun Nah, Park Jiha, Max Richter, The Waterboys, Bloc Party, Hubert-Félix-Thiéfaine, Reis-Demuth-Wiltgen, Paul Simon and Art Garfunkel, Paul Robeson, Ernest Melton, Didier Squiban, Connan Mockasin, Nina Simone, Merja Sonia, Chet Baker, Laïs, Joan Baez, Nils Frahm, Kate Bush, Megadeth, Radiohead


  • Chants des confins, jour 72 : Frankie Goes To Hollywood - Welcome to the pleasure dome
Life goes on days after day, the animals are winding me up, the jungle call
Shooting stars never stop, even when they reach the top
One of these days 
I'm going to cut you into little pieces
  • Chants des confins, jour 70 : Télépopmusik - Breathe
Another day, Just believe
Another day, Just breathe
When I am laid, am laid in earth, May my wrongs create
No trouble, no trouble in thy breast
  • Chants des confins, jour 68 : Villagers of Ioannina City - Age Of Aquarius
Stay close to the river and cry
And the river's gonna feel you're the god of rain
  • Chants des confins, jour 67 : Philip Glass played by Lavinia Meijer (harp) - Metamorphosis, Metamorphosis Two
  • Chants des confins, jour 66 : Dave Brubeck (and the Stranglers) - Golden Brown (kind of fake, caveat)
From far away
Stays for a day
  • Chants des confins, jour 65 : Mano Negra - Sidi'h'Bibi (album et live Chez Les Nuls L'Émission)
Ana m'rid ana m'rid
Hata m'rid mabia
And my skin was cool, And my heart sang
And when I said to myself that I will never go down

And there's a weepy old willow
He really knows how to cry
See the blind man shooting at the world
Bullets flying, oo-ooh taking toll
  • Chants des confins, jour 61 : The Kyteman Orchestra - PaDaDe (The Jam Sessions)
PaDaDe, PaDaDe, PaDaDe, PaDaDe, PaDaDe, PaDaDe, 
Part of the point in me doesn't know where to go, what I guess, it is all, just a show
  • Chants des confins, jour 60 : Dominique A (puis Alain Bashung) - Immortels
Avais-tu deviné que des dieux se cachaient
Sous nos faces avinées ?
  • Chants des confins, jour 59 : Vald - Barème
Mimi Mathy, reptile très petit
Pyramide, pentagone, pentacle et triple six
  • Chants des confins, jour 58 : George Frideric Handel - Duet "Son nata a lagrimar", from Giulio Cesare in Egitto (Nathalie Stutzmann & Philippe Jaroussky)
Son nata a lagrimar / Son nato a sospirar,
e il dolce mio conforto, ah, sempre piangerò.
Surely I'm a pionner
Constellations stay the same

  • Chants des confins, jour 56 : Têtes Raides - Bestiaire
La station en verticale
Pour tout vous dire c'est un fiasco
With love
  • Chants des confins, jour 54 : Sting - Fragile (Pat Metheny, Nils Landgren, Esbjörn Svensson, Michael Brecker, Lars Danielsson, Wolfgang Haffner; Jazz Baltica 2003)
On and on the rain will fall
Like tears from a star
  • Chants des confins, jour 53 : Andreas da Florentia/ Andrea de' Servi - Cosa crudel m'ancide (Ensemble Syntagma, Rosa e Orticha, music of the Trecento)
Se mai la vaga cosa di me fosse pietosa.
Morte da me decide.

  • Chants des confins, jour 52 : Ilene Barnes- Times
Do you ever go to shows
With their eyes to see?

  • Chants des confins, jour 51 : Marillion - Incubus
[and the other lyrics]
You who wiped me from your memory like a greasepaint mask, Just like a greasepaint mask
But now I'm the snake in the grass, the ghost of film reels past

But was that love in your eye I saw or the reflection of mine?
I'll never really know for sure, you never really gave me time
Darkness encloses
And the candle seems to expire
It's gonna be everything you've ever dreamed
It's gonna be who

  • Chants des confins, jour 47 : Osiris - Is It Time (rare Bahrain progressive rock)
People are faces that rarely smile
It's dark, but the brightness is blinding
See the blind man
Shooting at the world
Did you see the redness block your part?
Did the scissors cut a way to your heart?
Through the ages she's heading west
From far away

  • Chants des confins, jour 43 : Suzanne Vega - Luka
I think it's because I'm clumsy
I try not to talk too loud
A reclining figure, Made of brass and steel
It's a perfect mixture, How I think and feel
But how can we still be friends
When seeing you only breaks my heart again?
Die Zeit ist reif für ein bisschen Zärtlichkeit
Irgendwie irgendwo irgendwann
Stand by to stand by
Ain't no need to worry today
A bottle of whisky, And a new set of lies
Blinds on a window, And a pain behind the eyes
  • Chants des confins, jour 37 :  Microfilm - Dpt4
Witness Flight Lieutenant William Terrance Decker, Royal Flying Corps, returning from a patrol somewhere over France. The year is 1917. The problem is that the Lieutenant is hopelessly lost.
Lieutenant Decker will soon discover that a man can be lost not only in terms of maps and miles, but also in time, and time in this case can be measured in eternities. [Lyrics from the Twilight Zone, teleplay by Richard Matheson]
Vous pouvez m'appeler la nuit chez moi [...]
J'ai mangé, et j'ai eu envie de pleurer
A new warmth stirs within the center of the earth
I am alone here no more

The clock
Tik-tok
  • Chants des confins, jour 33 : Barclay James Harvest - 1978 Live Tapes, Mockingbird
There's a mocking bird
Singing songs in the trees
  • Chants des confins, jour 32 : Nancy Sinatra & Lee Hazlewood - Summer Wine
I walked in town on silver spurs that jingled to
A song that I had only sang to just a few
See the beast, choose the truth, follow your instinct
Cross the threshold, be an animal again

Freak out
I move with the crowd
It might be to late, To change where we're goin'
But in your own mind, You can always be free
Word are flowing out like and less rain into a paper cup,
They slither while they pass, they sleep across the Universe. [Jai Guru Deva Om: glory to the shining remover of darkness]
Ad te suspiramus, gementes et flentes in hac lacrimarum valle.
Eia, ergo, advocata nostra, illos tuos misericordes oculos ad nos converte.
  • Chants des confins, jour 26 : Yaron Herman - No Surprises (#Radiohead cover)
Bring down the government
They don't, they don't speak for us
  • Chants des confins, jour 25 : Samaris - Góða Tungl (from Steingrímur Þorsteinsson)
Góða tungl um loft þú líður,
Ljúft við skýja silfur skaut.
  • Chants des confins, jour 24 : Bel Canto (with the beautiful voice of Anneli Drecker) - Rumour
I bless the sunshine and no shadows haunt my walls
Blue is a state of mind, Blue makes you colourblind


  • Chants des confins, jour 23 : Sinéad O'Connor (and The Chieftains) - Factory Girl
Going back to the factory
Their work to begin

When the dog bites, When the bee stings
When I'm feeling sad, I simply remember my favorite things
[This multi-instrumentalist is so expressive that she makes me feel she sings]
[And she does. Titles are self-explanatory]

[Quote attributed to Plato: "We can easily forgive a child who is afraid of the dark;
the real tragedy of life is when men are afraid of the light."]
Now he rode East and he rode West, He rode North and South also
Until he came to a wide open plain, It was there that he spied his lady-o
We promised the world we'd tame it, what were we hoping for?
A sense of purpose and a sense of skill, a sense of function but a disregard
Dans les ruines de l'école où brûle un tableau noir
Une craie s'est brisée en écrivant : espoir. Kill the kid
[Instrumental. Title from an Greek legend about someone who buried a treasure after being defeated. The Oracle of Delphi advised researchers to look under every stone]
"(Toilet) Paper late!" cried a voice in the crowd
"Old man dies!" The note he left was signed 'Old Father Thames'
April, come she will, May, she will stay.
June, she'll changed her tune,  July, she will fly.
Yes ready for sorrow, And ready to suffer
Yes ready to fight 'til death

[Instrumental. Comment from Ernest Melton: "But it’s really a message to myself that, at the end of the day, I don’t have to be a slave to trivial stuff in my life. That’s all it is."]
(version instrumentale)
Neventi vad d'ar Vretoned! [Heureuse nouvelle aux Bretons !]
Ha malloz-ru d'ar C'hallaoued! [Et malédiction rouge aux Français !]
From Big West
That never change
Yes, I love the ground on where he goes
And still I hope

Aamulla varhain kun aurinko nousi (Early in the morning when the sun rose)
Yö oli kaunis ja äänesi hellä (The night was beautiful and your voice so tender)
Everyday that I awake, I must be mindful
That everyday is all I have to call my own
Il est perdu dans la nuit, La lune, la lune
houd uw kanneke proper Dianneke, houd uw kanneke vaste (x2)
But the cardboard-filled windows and old men on the benches
Tell you now that the whole town is empty
#plik 
#clank
I wake up crying
You're making rain
But now I'm safe in the eye of the tornado
I can't replace the lies, that let a 1000 days go
I'd be crazy not to follow
Follow where you lead your eyes

Forfait Joule : grandeurs et unités du temps de travail

[Article très provisoire, pour arriver à la notion professionnelle de "forfait Joule" #ToutCaPourCa] Quand on parle de travail que...