17.矩阵对角化-对称阵压缩

17.1 对称阵压缩的思想

设存在n阶对称阵A

现需对A中元素进行存储，则由对称阵性质知，A中有效元素个数=\(\frac{n\cdot(n+1)}{2}\)，即共需存储\(\frac{n\cdot(n+1)}{2}\)个元素

而由矩阵对角化性质可知，对于n阶对称阵A，若A的特征值各不相等，则必存在正交阵P使：

\[P \cdot A\cdot P^{-1}=P\cdot A \cdot P^T=\Lambda（\Lambda为n阶对角矩阵） \]

\[\Leftrightarrow P\cdot \Lambda \cdot P^T=A，则有： \]

\[[p_1,p_2,p_3,…,p_n]\cdot \begin{bmatrix} \lambda_1\\ &\lambda_2\\ &&…\\ &&&\lambda_n \end{bmatrix} \cdot \begin{bmatrix} p_1\\ p_2\\ p_3\\ …\\ p_n \end{bmatrix} =A \]

\[\tag{1} \Leftrightarrow \sum_{i=1}^{n} p_i\cdot\lambda_i\cdot p_i^T=A \]

17.2 对称阵压缩的方式

若直接由式（1）对A中元素进行存储，则：

\[由i=1,2,3,…,n得： \]

\[\begin{cases} (p_i=p^T_i)\Rightarrow p_i或p_i^T任选其一进行存储\\ 共n个p_i，任一p_i中有n个元素 \Rightarrow 需存储p_i中的n\cdot n个元素\\ \lambda值不重复\Rightarrow\lambda_i需存储n个\\ \end{cases} \]

\[\Rightarrow 共需存储n\cdot(n+1)个元素 \]

若式（1）中可保留前k项，舍去后n-k项，则：

\[由i=1,2,3,…,k得： \]

\[\begin{cases} (p_i=p^T_i)\Rightarrow p_i或p_i^T任选其一进行存储\\ 共k个p_i，任一p_i中有n个元素 \Rightarrow 需存储p_i中的k\cdot n个元素\\ \lambda值不重复\Rightarrow\lambda_i需存储k个\\ \end{cases} \]

\[\Rightarrow 共需存储k\cdot(n+1)个元素 \]

\[\Rightarrow 若k<\frac{n}{2}，则压缩有效 \]

17.3 对称阵压缩效率的评估

• 误差评估：

\[设err为对称阵压缩的误差率，则有： \]

\[\tag{2} err=\frac{\sum_{i=1}^k\lambda_i}{\sum_{i=1}^n\lambda_i}（err值越大，误差越小） \]

• 有效性评估：

\[设u为对称阵的压缩率，则有： \]

\[u=\frac{k\cdot(n+1)}{\frac{n\cdot (n+1)}{2}} \]

\[\tag{3} =\frac{2\cdot k}{n} \]

\[（u值越小，压缩有效性越高） \]

来源链接：https://www.cnblogs.com/efancn/p/18751431