Analyse en composantes indépendantes surcomplète via SDP.

Résumé Nous présentons un nouvel algorithme pour l'analyse en composantes indépendantes (ICA) surcomplète, où le nombre de sources latentes k dépasse la dimension p des variables observées. Les algorithmes précédents souffrent d'une complexité de calcul élevée ou font des hypothèses fortes sur la forme de la matrice de mélange. Notre algorithme ne fait aucune hypothèse de sparsité et bénéficie pourtant de propriétés informatiques et théoriques favorables. Notre algorithme se compose de deux étapes principales : (a) l'estimation des Hessiens de la fonction génératrice du cumulant (par opposition aux cumulants d'ordre 4 et plus utilisés par la plupart des algorithmes) et (b) une nouvelle relaxation de programmation semi-définie (SDP) pour récupérer une composante de mélange. Nous montrons que cette relaxation peut être résolue efficacement avec une méthode de descente de gradient accélérée projetée, ce qui rend l'algorithme entier pratique sur le plan informatique. De plus, nous conjecturons que le programme proposé récupère une composante de mélange au taux k < p^2/4 et nous prouvons qu'une composante de mélange peut être récupérée avec une probabilité élevée lorsque k < (2 - epsilon) p log p lorsque les composantes originales sont échantillonnées uniformément au hasard sur l'hyper sphère. Des expériences sont fournies sur des données synthétiques et sur le jeu de données CIFAR-10 d'images réelles.