Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/13F9D7BC-B98C-40E2-9705-5E257B3D5EFE | - |
| Αναγνωριστικό | https://doi.org/10.1109/TIT.2014.2303975 | - |
| Γλώσσα | en | - |
| Μέγεθος | 9 | en |
| Τίτλος | The sparse principal component of a constant-rank matrix | en |
| Δημιουργός | Asteris Megasthenis | en |
| Δημιουργός | Αστερης Μεγασθενης | el |
| Δημιουργός | Papailiopoulos, D.S | en |
| Δημιουργός | Karystinos Georgios | en |
| Δημιουργός | Καρυστινος Γεωργιος | el |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περιγραφή | Δημοσίευση σε επιστημονικό περιοδικό | el |
| Περίληψη | The computation of the sparse principal component of a matrix is equivalent to the identification of its principal submatrix with the largest maximum eigenvalue. Finding this optimal submatrix is what renders the problem NP-hard. In this paper, we prove that, if the matrix is positive semidefinite and its rank is constant, then its sparse principal component is polynomially computable. Our proof utilizes the auxiliary unit vector technique that has been recently developed to identify problems that are polynomially solvable. In addition, we use this technique to design an algorithm which, for any sparsity value, computes the sparse principal component with complexity O(ND+1), where N and D are the matrix size and rank, respectively. Our algorithm is fully parallelizable and memory efficient. | en |
| Τύπος | Peer-Reviewed Journal Publication | en |
| Τύπος | Δημοσίευση σε Περιοδικό με Κριτές | el |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-10-23 | - |
| Ημερομηνία Δημοσίευσης | 2014 | - |
| Θεματική Κατηγορία | Eigenvalues and eigenfunctions | en |
| Θεματική Κατηγορία | feature extraction | en |
| Θεματική Κατηγορία | information processing | en |
| Θεματική Κατηγορία | machine learning algorithms | en |
| Θεματική Κατηγορία | principal component analysis | en |
| Θεματική Κατηγορία | signal processing algorithms | en |
| Βιβλιογραφική Αναφορά | M. Asteris, D. S. Papailiopoulos, and G. N. Karystinos, "The sparse principal component of a constant-rank matrix," IEEE Transactions on Information Theory,vol. 60, no. 4, pp. 2281 - 2290, Apr. 2014. doi: 10.1109/TIT.2014.2303975 | en |
Copyright © DIAS 2013
