A geometric approach to archetypal analysis via sparse projections
AUTHORs: 
V. Abrol, P. SharmaAuthors Info & Claims
Article No.: 5, Pages 42 - 51
Abstract
Archetypal analysis (AA) aims to extract patterns using self-expressive decomposition of data as convex combinations of extremal points (on the convex hull) of the data. This work presents a computationally efficient greedy AA (GAA) algorithm. GAA leverages the underlying geometry of AA, is scalable to larger datasets, and has significantly faster convergence rate. To achieve this, archetypes are learned via sparse projection of data. In the transformed space, GAA employs an iterative subset selection approach to identify archetypes based on the sparsity of convex representations. The work further presents the use of GAA algorithm for extended AA models such as robust and kernel AA. Experimental results show that GAA is considerably faster while performing comparable to existing methods for tasks such as classification, data visualization/categorization.
Supplementary Material
Supplemental material.
- Download
- 651.35 KB
References
[1]
Abrol, V., Sharma, P., and Sao, A. Greedy dictionary learning for kernel sparse representation based classifier. Pattern Recognition Letters, 78:64 - 69, 2016. ISSN 0167- 8655.
[2]
Abrol, V., Sharma, P., and Sao, A. K. Fast exemplar selection algorithm for matrix approximation and representation: A variant oasis algorithm. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4436-4440, March 2017.
[3]
Adele Cutler, L. B. Archetypal analysis. Technometrics, 36 (4):338-347, November 1994. ISSN 00401706.
[4]
Arora, S., Ge, R., Kannan, R., and Moitra, A. Computing a nonnegative matrix factorization - provably. In Annual ACM Symposium on Theory of Computing (STOC), pp. 145-162, New York, NY, USA, May 2012.
[5]
Bache, K. and Lichman, M. UCI machine learning repository, 2013. URL http://archive.ics.uci.edu/ml.
[6]
Bauckhage, C. and Manshaei, K. Kernel archetypal analysis for clustering web search frequency time series. In International Conference on Pattern Recognition (ICPR), pp. 1544-1549, August 2014.
[7]
Bauckhage, C., Kersting, K., Hoppe, F., and Thurau, C. Archetypal analysis as an autoencoder. In Workshop on New Challenges in Neural Computation, pp. 8-15, October 2015.
[8]
Bernstein, D. Matrix Mathematics: Theory, Facts, and Formulas (Second Edition). Princeton reference. Princeton University Press, 2009. ISBN 9780691140391.
[9]
Cabero, I. and Epifanio, I. Archetypal analysis: An alternative to clustering for unsupervised texture segmentation. Image Analysis and Stereology, 38(2):151-160, 2019. ISSN 1854-5165.
[10]
Chen, W., Rodrigues, M., and Wassell, I. Projection design for statistical compressive sensing: A tight frame based approach. IEEE Transactions on Signal Processing, 61 (8):2016-2029, April 2013. ISSN 1053-587X.
[11]
Chen, Y., Mairal, J., and Harchaoui, Z. Fast and robust archetypal analysis for representation learning. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1478-1485, June 2014. ISBN 978-1-4799-5118-5.
[12]
Chu, M. T. and Lin, M. M. Low-dimensional polytope approximation and its applications to nonnegative matrix factorization. SIAM Journal on Scientific Computing, 30 (3):1131-1155, 2008.
[13]
Damle, A. and Sun, Y. A geometric approach to archetypal analysis and nonnegative matrix factorization. Technometrics, 59(3):361-370, 2017.
[14]
Das, A. and Kempe, D. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In International Conference on Machine Learning (ICML), pp. 1057-1064, June 2011. ISBN 978-1-4503-0619-5.
[15]
Diment, A. and Virtanen, T. Archetypal analysis for audio dictionary learning. In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics (WASPAA), pp. 1-5, October 2015.
[16]
Ding, W., Ishwar, P., and Saligrama, V. A provably efficient algorithm for separable topic discovery. IEEE Journal of Selected Topics in Signal Processing, 10(4):712-725, June 2016. ISSN 1941-0484.
[17]
Elhamifar, E., Sapiro, G., and Vidal, R. See all by looking at a few: Sparse modeling for finding representative objects. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1600-1607, June 2012.
[18]
Epifanio, I., Ibáñez, M. V., and Simó, A. Archetypal analysis with missing data: See all samples by looking at a few based on extreme profiles. The American Statistician, 0 (0):1-28, 2019.
[19]
Eugster, M. J. and Leisch, F. Weighted and robust archetypal analysis. Computational Statistics and Data Analysis, 55(3):1215 - 1225, May 2011. ISSN 0167-9473.
[20]
Fotiadou, E., Panagakis, Y., and Pantic, M. Temporal archetypal analysis for action segmentation. In IEEE International Conference on Automatic Face Gesture Recognition, pp. 490-496, May 2017.
[21]
Hinrich, J. L., Bardenfleth, S. E., Røge, R. E., Churchill, N. W., Madsen, K. H., and Mørup, M. Archetypal analysis for modeling multisubject fMRI data. IEEE Journal of Selected Topics in Signal Processing, 10 (7):1160-1171, October 2016. ISSN 1932-4553.
[22]
Hurley, N. and Rickard, S. Comparing measures of sparsity. IEEE Transactions on Information Theory, 55(10):4723- 4741, October 2009.
[23]
Jafari, M. and Plumbley, M. Fast dictionary learning for sparse representations of speech signals. IEEE Journal of Selected Topics in Signal Processing, 5(5):1025-1031, September 2011. ISSN 1932-4553.
[24]
Javadi, H. and Montanari, A. Nonnegative matrix factorization via archetypal analysis. Journal of the American Statistical Association, 0(0):1-22, 2019.
[25]
Krause, A., Singh, A., and Guestrin, C. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9:235-284, June 2008. ISSN 1532- 4435.
[26]
Mair, S. and Brefeld, U. Coresets for archetypal analysis. In Advances in Neural Information Processing Systems (NeurIPS), pp. 7245-7253, December 2019.
[27]
Mair, S., Boubekki, A., and Brefeld, U. Frame-based data factorizations. In International Conference on Machine Learning (ICML), pp. 2305-2313, August 2017.
[28]
McCallum, D. and Avis, D. A linear algorithm for finding the convex hull of a simple polygon. Information Processing Letters, 9(5):201 - 206, December 1979. ISSN 0020-0190.
[29]
Mei, J., Wang, C., and Zeng, W. Online dictionary learning for approximate archetypal analysis. In European Conference on Computer Vision (ECCV), pp. 501-516, September 2018.
[30]
Moliner, J. and Epifanio, I. Robust multivariate and functional archetypal analysis with application to financial time series analysis. Physica A: Statistical Mechanics and its Applications, 519:195 - 208, 2019. ISSN 0378- 4371.
[31]
Mørup, M. and Hansen, L. K. Archetypal analysis for machine learning and data mining. Neurocomputing: Special Issue on Machine Learning for Signal Processing, 80:54 - 63, March 2012. ISSN 0925-2312.
[32]
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14(1):265- 294, December 1978. ISSN 1436-4646.
[33]
Seth, S. and Eugster, M. Archetypal analysis for nominal observations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 38(5):849-861, May 2016a. ISSN 0162-8828.
[34]
Seth, S. and Eugster, M. J. A. Probabilistic archetypal analysis. Machine Learning, 102(1):85-113, January 2016b. ISSN 1573-0565.
[35]
Thakur, A., Abrol, V., Sharma, P., and Rajan, P. Local compressed convex spectral embedding for bird species identification. The Journal of the Acoustical Society of America, 143(6):3819-3828, 2018.
[36]
Thurau, C. and Bauckhage, C. Archetypal images in large photo collections. In IEEE International Conference on Semantic Computing (ICSC), pp. 129-136, September 2009.
[37]
Thurau, C., Kersting, K., Wahabzada, M., and Bauckhage, C. Convex non-negative matrix factorization for massive datasets. Knowledge and Information Systems, 29(2):457- 478, November 2011.
[38]
Tosic, I. and Frossard, P. Dictionary learning. IEEE Signal Processing Magazine, 28(2):27-38, March 2011. ISSN 1053-5888.
[39]
Van Nguyen, H., Patel, V., Nasrabadi, N., and Chellappa, R. Design of non-linear kernel dictionaries for object recognition. IEEE Transactions on Image Processing, 22 (12):5123-5135, December 2013.
[40]
Wynen, D., Schmid, C., and Mairal, J. Unsupervised learning of artistic styles with archetypal style analysis. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6584-6593, 2018.
[41]
Xiao, J., Hays, J., Ehinger, K. A., Oliva, A., and Torralba, A. Sun database: Large-scale scene recognition from abbey to zoo. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 3485-3492, June 2010.
[42]
Yale Song, Vallmitjana, J., Stent, A., and Jaimes, A. TVSum: summarizing web videos using titles. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 5179-5187, June 2015.
[43]
Zhao, C., Zhao, G., and Jia, X. Hyperspectral image unmixing based on fast kernel archetypal analysis. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing, PP(99):1-16, September 2016. ISSN 1939-1404.
[44]
Zhao, G., Zhao, C., and Jia, X. Multilayer unmixing for hyperspectral imagery with fast kernel archetypal analysis. IEEE Geoscience and Remote Sensing Letters, 13(10): 1532-1536, October 2016.
[45]
Zhou, T., Bilmes, J., and Guestrin, C. Divide-and-conquer learning by anchoring a conical hull. In International Conference on Neural Information Processing Systems (NIPS), pp. 1242-1250, December 2014.
Recommendations
Regression analysis of locality preserving projections via sparse penalty
Recent studies have shown that linear subspace algorithms, such as Principal Component Analysis, Linear Discriminant Analysis and Locality Preserving Projections, have attracted tremendous attention in many fields of information processing. However, the ...
Sparse Regularization via Convex Analysis
Sparse approximate solutions to linear equations are classically obtained via L1 norm regularized least squares, but this method often underestimates the true solution. As an alternative to the L1 norm, this paper proposes a class of nonconvex penalty ...
Sparse projections onto the simplex
ICML'13: Proceedings of the 30th International Conference on International Conference on Machine Learning - Volume 28Most learning methods with rank or sparsity constraints use convex relaxations, which lead to optimization with the nuclear norm or the l1-norm. However, several important learning applications cannot benefit from this approach as they feature these ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2020.
Publisher
JMLR.org
Publication History
Published: 13 July 2020
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 102Total Downloads
- Downloads (Last 12 months)80
- Downloads (Last 6 weeks)22
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in