【摘要】：与奇异值分解算法所生成的左、右奇异向量矩阵不同的是，ACA算法所生成的逼近矩阵分解因子中各向量间并不存在正交的良好性质，换言之，矩阵中存储的信息可能存在着冗余，因此存在着进一步压缩的可能。
与奇异值分解算法所生成的左、右奇异向量矩阵不同的是，ACA算法所生成的逼近矩阵分解因子中各向量间并不存在正交的良好性质，换言之，矩阵中存储的信息可能存在着冗余，因此存在着进一步压缩的可能。
已知矩阵M∈Cm×n，可近似分解为 M ≈ UVT，其中U∈Cm×k，V∈Ck×n，对U和VT分别进行QR分解，得到：
其中QU∈Cm×k，QVT∈Cn×k，而RU，RVT∈Ck×k是两个上三角矩阵。令S=RU*RVTT，则有S∈Ck×k，设矩阵S的秩为r，则对S进行奇异值分解，得到：
其中US∈Ck×r，∑S∈Cr×r，VS∈Cr×k，r≤k。由此可以得到重压缩后的近似表达式：(www.xing528.com)
其中U*∈Cm×r，V*∈Cr×n。
分别对U和V进行QR分解的计算复杂度为O（k2（m+n）），而对S进行奇异值分解的计算复杂度为O（k3），利用分解因子计算出重压缩后的近似矩阵因子U*和V*需进行两次矩阵乘法，其计算复杂度同样为O（k2（m+n）），因此可以粗略估计出整个重压缩过程的计算复杂度为O（k2（m+n+k））。根据上文的讨论我们知道，当输入矩阵M是由某个满足渐进光滑特性的函数f导出时，其近似矩阵的秩与矩阵的维数的对数呈线性关系，因此k相对于m、n而言只是一个小量，即使在重压缩算法的计算复杂度中出现了k2的因子，仍然不会对ACA算法的计算量造成明显的影响。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
