数据挖掘 - 如何计算矩阵逆计算的特定时间复杂度？ - 吾爱随笔录

数据挖掘数据挖掘算法

2021-10-13 04:52:26

我是计算时间复杂度的新手。给定如下计算：

x = A^{T} (A A^{T} + λ I_{n})^{- 1} b

$\begin{equation} \mathbf{x}=\mathbf{A^T}(\mathbf{AA^T}+\lambda\mathbf{I}_n)^{-1}\mathbf{b} \end{equation}$ 在哪里

A \in R^{n \times p}

$\mathbf{A}\in R^{n\times p}$ ,

I_{n} \in R^{n \times n}

$\mathbf{I}_n\in R^{n\times n}$ ,

b \in R^{n}

$\mathbf{b}\in R^{n}$ 和

λ \in R

$\lambda\in R$ .

有人可以详细告诉我上述公式的复杂性吗？非常感谢。

2个回答

如果您需要以大 O 表示法计算的复杂性 - 它是：

O (n^{3})

$O(n^3)$ 为什么？因为矩阵求逆需要

O (n^{3})

$O(n^3)$ 操作，这是最大的复杂性。

其转置的乘法矩阵是

O (n^{2} p)

$O(n^2p)$ （因为要计算大小为 NxN 的结果矩阵中的每个值，您必须计算 p 次乘法）。矩阵转置是

O (n p)

$O(np)$ 但是你可以忽略任何小于

O (n^{3})

$O(n^3)$ （如矩阵求和、转置或乘以常数）因为它们的增长顺序远小于逆运算的增长顺序。

@Olologin 对于没有优化的非常基本的直接求解是正确的，但是存在优化，所以我想补充几点......

许多数学家将整个职业生涯都花在加速和优化这个问题上。因此，解决方案在很大程度上取决于矩阵 ( sparsity) 的组成，问题是否是convex，是否正在解决iteratively，directly以及正在使用什么算法。

对于许多数据科学问题 $O(n^2)$ 并且容易获得更好的解决方案。

一些常见的库包括：

以下是对该主题的一些调查：

其它你可能感兴趣的问题