Sparse PCA on fixed-rank matrices. (English) Zbl 1512.90157
Summary: Sparse PCA is the optimization problem obtained from PCA by adding a sparsity constraint on the principal components. Sparse PCA is NP-hard and hard to approximate even in the single-component case. In this paper we settle the computational complexity of sparse PCA with respect to the rank of the covariance matrix. We show that, if the rank of the covariance matrix is a fixed value, then there is an algorithm that solves sparse PCA to global optimality, whose running time is polynomial in the number of features. We also prove a similar result for the version of sparse PCA which requires the principal components to have disjoint supports.
MSC:
| 90C20 | Quadratic programming |
| 90C26 | Nonconvex programming, global optimization |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
principal component analysis; sparsity; polynomial-time algorithm; global optimum; constant-rank quadratic functionSoftware:
Optimal-SPCAReferences:
| [1] | Asteris, M., Papailiopoulos, D., Karystinos, G.: Sparse principal component of a rank-deficient matrix. In: Proceedings of ISIT (2011) |
| [2] | Asteris, M.; Papailiopoulos, D.; Karystinos, G., The sparse principal component of a constant-rank matrix, IEEE Trans. Inf. Theor., 60, 4, 2281-2290 (2014) · Zbl 1360.94059 · doi:10.1109/TIT.2014.2303975 |
| [3] | Asteris, M., Papailiopoulos, D., Kyrillidis, A., Dimakis, A.: Sparse PCA via bipartite matchings. In: Proceedings of NIPS (2015) |
| [4] | Berk, L.; Bertsimas, D., Certifiably optimal sparse principal component analysis, Math. Progr. Comput., 11, 381-420 (2019) · Zbl 1435.62214 · doi:10.1007/s12532-018-0153-6 |
| [5] | Bertsimas, D.; Tsitsiklis, J., Introduction to Linear Optimization (1997), Belmont: Athena Scientific, Belmont |
| [6] | Boutsidis, C., Drineas, P., Magdon-Ismail, M.: Sparse features for PCA-like linear regression. In: Proceedings of NIPS, pp. 2285-2293 (2011) |
| [7] | Cadima, J.; Jolliffe, I., Loading and correlations in the interpretation of principle compenents, J. Appl. Stat., 22, 2, 203-214 (1995) · doi:10.1080/757584614 |
| [8] | Chan, S., Papailiopoulos, D., Rubinstein, A.: On the worst-case approximability of sparse PCA. Proceedings of COLT (2016) |
| [9] | d’Aspremont, A.; Bach, F.; Ghaoui, L., Optimal solutions for sparse principal component analysis, J. Mach. Learning Res., 9, 1269-1294 (2008) · Zbl 1225.68170 |
| [10] | d’Aspremont, A., Bach, F., Ghaoui, L.: Approximation bounds for sparse principal component analysis. Mathematical Programming Series . 148(1), pp. 89-110 · Zbl 1303.90079 |
| [11] | d’Aspremont, A., El Ghaoui, L., Jordan, M., Lanckriet, G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49(3), 434-448 (2007) · Zbl 1128.90050 |
| [12] | Dey, S., Mazumder, R., Wang, G.: A convex integer programming approach for optimal sparse PCA. arXiv preprint arXiv:1810.09062 (2018) |
| [13] | Edelsbrunner, H.; O’Rourke, J.; Seidel, R., Constructing arrangements of lines and hyperplanes with applications, SIAM J. Comput., 15, 2, 341-363 (1986) · Zbl 0603.68104 · doi:10.1137/0215024 |
| [14] | Goldberg, A., Tarjan, R.: Finding minimum-cost circulations by canceling negative cycles. In: Proceedings of STOC, pp. 388-397 (1988) |
| [15] | Goldberg, A.; Tarjan, R., Finding minimum-cost circulations by canceling negative cycles, J. Assoc. Comput. Mach., 36, 873-886 (1989) · Zbl 0697.68063 · doi:10.1145/76359.76368 |
| [16] | Hastie, T.; Tibshirani, R.; Wainwright, M., Stat. learning Sparsity (2015), Boca Raton: CRC Press, Boca Raton · Zbl 1319.68003 · doi:10.1201/b18401 |
| [17] | He, Y., Monteiro, R., Park, H.: An efficient algorithm for rank-1 sparse PCA. In: working paper (2010) |
| [18] | Jolliffe, I.; Trendafilov, N.; Uddin, M., A modified principal component technique based on the lasso, J. Comput. Graph. Stat., 12, 3, 531-547 (2003) · doi:10.1198/1061860032148 |
| [19] | Journée, M.; Nesterov, Y.; Richtárik, P.; Sepulchre, R., Generalized power method for sparse principal component analysis, J. Mach. Learn. Res., 11, 517-553 (2010) · Zbl 1242.62048 |
| [20] | Karystinos, G.; Liavas, A., Efficient computation of the binary vector that maximizes a rank-deficient quadratic form, IEEE Trans. Inf. Theor., 56, 7, 3581-3593 (2010) · Zbl 1366.94145 · doi:10.1109/TIT.2010.2048450 |
| [21] | Karystinos, G.; Pados, D., Rank-2-optimal adaptive design of binary spreading codes, IEEE Trans. Inf. Theor., 53, 9, 3075-3080 (2007) · Zbl 1325.94080 · doi:10.1109/TIT.2007.903130 |
| [22] | Mackenthun, K., A fast algorithm for multiple-symbol differential detection of MPSK, IEEE Trans. Commun., 42, 234, 1471-1474 (1994) · doi:10.1109/TCOMM.1994.582823 |
| [23] | Mackey, L.: Deflation methods for sparse PCA. In: Proceedings of NIPS, vol. 21, pp. 1017-1024 (2009) |
| [24] | Magdon-Ismail, M., NP-hardness and inapproximability of sparse PCA, Inf. Process. Lett., 126, 35-38 (2017) · Zbl 1407.68406 · doi:10.1016/j.ipl.2017.05.008 |
| [25] | Moghaddam, B., Weiss, Y., Avidan, S.: Spectral bounds for sparse PCA: exact and greedy algorithms. In: Proceedings of NIPS, vol. 18, p. 915 (2006) |
| [26] | Motedayen, I.; Krishnamoorthy, A.; Anastasopoulos, A., Optimal joint detection/estimation in fading channels with polynomial complexity, IEEE Trans. Inf. Theor., 53, 1, 209-223 (2007) · Zbl 1310.94194 · doi:10.1109/TIT.2006.887504 |
| [27] | Papailiopoulos, D., Dimakis, A., Korokythakis, S.: Sparse PCA through low-rank approximations. In: Proceedings of ICML (2013) |
| [28] | Schrijver, A., Combinatorial Optimization . Polyhedra and Efficiency (2003), Berlin: Springer-Verlag, Berlin · Zbl 1041.90001 |
| [29] | Shalev-Shwartz, S.; Ben-David, S., Understanding Machine Learning (2014), Cambridge: Cambridge University Press, Cambridge · Zbl 1305.68005 · doi:10.1017/CBO9781107298019 |
| [30] | Sigg, C., Buhmann, J.: Expectation-maximization for sparse and non-negative PCA. In: Proceedings of ICML, pp. 960-967 (2008) |
| [31] | Sweldens, W., Fast block noncoherent decoding, IEEE Commun. Lett., 5, 4, 132-134 (2001) · doi:10.1109/4234.917091 |
| [32] | Vu, V., Lei, J.: Minimax rates of estimation for sparse PCA in high dimensions. In: Proceedings of AIStats, pp. 1278-1286 (2012) |
| [33] | Yuan, X.; Zhang, T., Truncated power method for sparse eigenvalue problems, J. Mach. Learn. Res., 14, 899-925 (2013) · Zbl 1320.62141 |
| [34] | Zhang, Y.; d’Aspremont, A.; Ghaoui, LE; Anjos, M.; Lasserre, J., Sparse PCA: convex relaxations, algorithms and applications, Handbook on Semidefinite, Conic and Polynomial Optimization, 915-940 (2011), Boston, MA: Springer, Boston, MA · Zbl 1334.90120 · doi:10.1007/978-1-4614-0769-0_31 |
| [35] | Zou, H.; Hastie, T.; Tibshirani, R., Sparse principal component analysis, J. Comput. Graph. Stat., 15, 2, 265-286 (2006) · doi:10.1198/106186006X113430 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
