Я читал статью о Sparse PCA: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf
И в нем говорится, что если у вас есть n точки данных, каждая из которых представлена p функциями, то сложность PCA составляет O(min(p^3,n^3)).
Может кто-нибудь объяснить, как/почему?
Вычисление ковариационной матрицы — O(p2n); его разложение по собственным значениям равно O(p3). Таким образом, сложность PCA равна O(p2n+p3).
O(min(p3,n3)) означает, что вы можете анализировать двумерный набор данных любого размера за фиксированное время, что явно неверно.
Предполагая, что ваш набор данных равен $X \in \R^{nxp}$, где n: количество выборок, d: размеры выборки, вас интересует собственный анализ $X^TX$, который является основной вычислительной стоимостью PCA. Теперь матрицы $X^TX \in \R^{pxp}$ и $XX^T \in \R^{nxn}$ имеют одинаковые min(n, p) неотрицательные собственные значения и собственные векторы. Предполагая, что p меньше n, вы можете решить собственный анализ в $O(p^3)$. Если p больше n (например, в компьютерном зрении во многих случаях размерность выборки — количество пикселей — больше, чем количество доступных выборок), вы можете выполнить собственный анализ за время $O(n^3)$. В любом случае вы можете получить собственные векторы одной матрицы из собственных значений и собственных векторов другой матрицы и сделать это за время $O(min(p, n)^3)$.
$$X^TX = V \Lambda V^T$$
$$XX^T = U \Lambda U^T$$
$$U = XV\лямбда^{-1/2}$$
Ниже приведен ответ Майкла, представленный как в оригинальном LaTeX, так и в формате PNG.
Латекс код:
Предполагая, что ваш набор данных равен $X \in R^{n\times p}$, где n: количество выборок, p: размеры выборки, вас интересует собственный анализ $X^TX$, который является основной вычислительной стоимостью СПС. Теперь матрицы $X^TX \in \R^{p \times p}$ и $XX^T \in \R^{n\times n}$ имеют одинаковые min(n, p) неотрицательные собственные значения и собственные векторы. Предполагая, что p меньше n, вы можете решить собственный анализ в $O(p^3)$. Если p больше n (например, в компьютерном зрении во многих случаях размерность выборки — количество пикселей — больше, чем количество доступных выборок), вы можете выполнить собственный анализ за время $O(n^3)$. В любом случае вы можете получить собственные векторы одной матрицы из собственных значений и собственных векторов другой матрицы и сделать это за время $O(min(p, n)^3)$.
