Vi anser att problemet med att identifiera den glesa huvudkomponenten i en rank-brist matris. Vi introducerar extra sfäriska variabler och bevisar att det finns en uppsättning kandidatindex-uppsättningar (dvs. uppsättningar av index till icke-noll elementen i vektor argumentet) vars storlek är polynomiskt avgränsad, i termer av rank, och innehåller den optimala indexuppsättningen, dvs.. indexuppsättningen av icke-nollelementen i den optimala lösningen. Slutligen utvecklar vi en algoritm som beräknar den optimala glesa huvudkomponenten i polynom tid för någon gleshet grad.
En algoritm som löser gles PCA för konstant rang matriser i polynom tid infördes i REF.
Sparse principal component of a rank-deficient matrix
{'venue': '2011 IEEE International Symposium on Information Theory Proceedings', 'journal': '2011 IEEE International Symposium on Information Theory Proceedings', 'mag_field_of_study': ['Mathematics', 'Computer Science']}