Frame-based Data Factorizations

Sebastian Mair, Ahcène Boubekki, Ulf Brefeld
; Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2305-2313, 2017.

Abstract

Archetypal Analysis is the method of choice to compute interpretable matrix factorizations. Every data point is represented as a convex combination of factors, i.e., points on the boundary of the convex hull of the data. This renders computation inefficient. In this paper, we show that the set of vertices of a convex hull, the so-called frame, can be efficiently computed by a quadratic program. We provide theoretical and empirical results for our proposed approach and make use of the frame to accelerate Archetypal Analysis. The novel method yields similar reconstruction errors as baseline competitors but is much faster to compute.

Cite this Paper


BibTeX
@InProceedings{pmlr-v70-mair17a, title = {Frame-based Data Factorizations}, author = {Sebastian Mair and Ahc{\`e}ne Boubekki and Ulf Brefeld}, pages = {2305--2313}, year = {2017}, editor = {Doina Precup and Yee Whye Teh}, volume = {70}, series = {Proceedings of Machine Learning Research}, address = {International Convention Centre, Sydney, Australia}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/mair17a/mair17a.pdf}, url = {http://proceedings.mlr.press/v70/mair17a.html}, abstract = {Archetypal Analysis is the method of choice to compute interpretable matrix factorizations. Every data point is represented as a convex combination of factors, i.e., points on the boundary of the convex hull of the data. This renders computation inefficient. In this paper, we show that the set of vertices of a convex hull, the so-called frame, can be efficiently computed by a quadratic program. We provide theoretical and empirical results for our proposed approach and make use of the frame to accelerate Archetypal Analysis. The novel method yields similar reconstruction errors as baseline competitors but is much faster to compute.} }
Endnote
%0 Conference Paper %T Frame-based Data Factorizations %A Sebastian Mair %A Ahcène Boubekki %A Ulf Brefeld %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-mair17a %I PMLR %J Proceedings of Machine Learning Research %P 2305--2313 %U http://proceedings.mlr.press %V 70 %W PMLR %X Archetypal Analysis is the method of choice to compute interpretable matrix factorizations. Every data point is represented as a convex combination of factors, i.e., points on the boundary of the convex hull of the data. This renders computation inefficient. In this paper, we show that the set of vertices of a convex hull, the so-called frame, can be efficiently computed by a quadratic program. We provide theoretical and empirical results for our proposed approach and make use of the frame to accelerate Archetypal Analysis. The novel method yields similar reconstruction errors as baseline competitors but is much faster to compute.
APA
Mair, S., Boubekki, A. & Brefeld, U.. (2017). Frame-based Data Factorizations. Proceedings of the 34th International Conference on Machine Learning, in PMLR 70:2305-2313

Related Material