Overcomplete Independent Component Analysis via SDP

Anastasia Podosinnikova, Amelia Perry, Alexander S. Wein, Francis Bach, Alexandre d’Aspremont, David Sontag
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:2583-2592, 2019.

Abstract

We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous algorithms either suffer from high computational complexity or make strong assumptions about the form of the mixing matrix. Our algorithm does not make any sparsity assumption yet enjoys favorable computational and theoretical properties. Our algorithm consists of two main steps: (a) estimation of the Hessians of the cumulant generating function (as opposed to the fourth and higher order cumulants used by most algorithms) and (b) a novel semi-definite programming (SDP) relaxation for recovering a mixing component. We show that this relaxation can be efficiently solved with a projected accelerated gradient descent method, which makes the whole algorithm computationally practical. Moreover, we conjecture that the proposed program recovers a mixing component at the rate $k < p^2/4$ and prove that a mixing component can be recovered with high probability when $k <(2 - \epsilon)p\log p$ when the original components are sampled uniformly at random on the hyper sphere. Experiments are provided on synthetic data and the CIFAR-10 dataset of real images.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-podosinnikova19a, title = {Overcomplete Independent Component Analysis via SDP}, author = {Podosinnikova, Anastasia and Perry, Amelia and Wein, Alexander S. and Bach, Francis and d'Aspremont, Alexandre and Sontag, David}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {2583--2592}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/podosinnikova19a/podosinnikova19a.pdf}, url = {https://proceedings.mlr.press/v89/podosinnikova19a.html}, abstract = {We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous algorithms either suffer from high computational complexity or make strong assumptions about the form of the mixing matrix. Our algorithm does not make any sparsity assumption yet enjoys favorable computational and theoretical properties. Our algorithm consists of two main steps: (a) estimation of the Hessians of the cumulant generating function (as opposed to the fourth and higher order cumulants used by most algorithms) and (b) a novel semi-definite programming (SDP) relaxation for recovering a mixing component. We show that this relaxation can be efficiently solved with a projected accelerated gradient descent method, which makes the whole algorithm computationally practical. Moreover, we conjecture that the proposed program recovers a mixing component at the rate $k < p^2/4$ and prove that a mixing component can be recovered with high probability when $k <(2 - \epsilon)p\log p$ when the original components are sampled uniformly at random on the hyper sphere. Experiments are provided on synthetic data and the CIFAR-10 dataset of real images.} }
Endnote
%0 Conference Paper %T Overcomplete Independent Component Analysis via SDP %A Anastasia Podosinnikova %A Amelia Perry %A Alexander S. Wein %A Francis Bach %A Alexandre d’Aspremont %A David Sontag %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-podosinnikova19a %I PMLR %P 2583--2592 %U https://proceedings.mlr.press/v89/podosinnikova19a.html %V 89 %X We present a novel algorithm for overcomplete independent components analysis (ICA), where the number of latent sources k exceeds the dimension p of observed variables. Previous algorithms either suffer from high computational complexity or make strong assumptions about the form of the mixing matrix. Our algorithm does not make any sparsity assumption yet enjoys favorable computational and theoretical properties. Our algorithm consists of two main steps: (a) estimation of the Hessians of the cumulant generating function (as opposed to the fourth and higher order cumulants used by most algorithms) and (b) a novel semi-definite programming (SDP) relaxation for recovering a mixing component. We show that this relaxation can be efficiently solved with a projected accelerated gradient descent method, which makes the whole algorithm computationally practical. Moreover, we conjecture that the proposed program recovers a mixing component at the rate $k < p^2/4$ and prove that a mixing component can be recovered with high probability when $k <(2 - \epsilon)p\log p$ when the original components are sampled uniformly at random on the hyper sphere. Experiments are provided on synthetic data and the CIFAR-10 dataset of real images.
APA
Podosinnikova, A., Perry, A., Wein, A.S., Bach, F., d’Aspremont, A. & Sontag, D.. (2019). Overcomplete Independent Component Analysis via SDP. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:2583-2592 Available from https://proceedings.mlr.press/v89/podosinnikova19a.html.

Related Material