写在前面

近期讨论的时候涉及到这篇文章^[1]，记录下创新点。

平稳信号去噪相关研究

• 线性滤波器：需要计算信号和噪声的自相关和互相关矩阵，需修改线宽
• 多分辨率分析：比传统的正交方法更有效
• 基于统计的方法：需要预先知道频率的个数，用奇异值分解计算复杂度高
• 随机投影和概率算法：可避免数据的显式计算

随机QR算法

本文所提出的随机算法是对数据矩阵进行下采样，投影后的数据保留了原始数据的大致特征，因此实现概率意义下的降维。下面是算法具体步骤：

1. 将由$P$个阻尼正弦信号组成的谐波$X$Hankel化

   $$H_{i,j}\leftarrow X_{i+j-1}$$

   • 在无噪声情况下，矩阵$H$的秩为$P$
   • 在含噪声情况下，矩阵$H$是满秩的

2. 生成随机矩阵$\Omega$，其中元素$\Omega_{ij}\sim\mathcal N(0,1)$。计算投影矩阵

   $$\underset{(M \times K)}{Y}\leftarrow\underset{(M \times N)}{H}\times\underset{(N \times K)}{\Omega}$$

   矩阵$Y$的尺寸比矩阵$H$的要小$K\leq M$，因此在保留原始信息的同时降低维度，为后续的分解降低计算复杂度。

3. 对$Y$进行QR分解

   $$(Q,R)\leftarrow\text{QR}(Y)$$

   正交阵$Q$可以作为矩阵$H$的降秩正交基，可得到矩阵$H$的秩$K$正交投影

   $$\tilde{H}\leftarrow QQ^* H$$

   令$p=K-P$，此近似值在谱范数意义下的界如下

   $$\|H-\tilde{H}\|\leq[1+9\sqrt{KM}]_{\sigma_{P+1}}$$

   其中$\sigma_{P+1}$是矩阵$H$的第$P+1$个奇异值。该上界存在的概率大于$1-3p^{-p}$。

4. 反对角平均得到去噪后的信号$\tilde{X}$

   $$\tilde{X}_l\leftarrow \operatorname*{mean}_{i+k=l+1}(\tilde{H}_{ij})$$

rQRd算法流程

快速Hankel矩阵乘积

利用快速Fourier变换，Hankel矩阵的矩阵-向量乘积可得到快速的实现。

• Hankel矩阵与向量乘积：将矩阵和向量做FFT变换，对应位置乘积后做逆FFT变换得到结果，见FHV。
• Hankel矩阵与矩阵乘积：将乘数矩阵按列展开，利用Hankel矩阵与向量乘积得到矩阵乘积结果，见FHM。

具体流程如下：

回顾到随机QR去噪算法的投影和对角平均过程：

$$\tilde{H}= QQ^* H, \tilde{X}_l= \operatorname*{mean}_{i+k=l+1}(\tilde{H}_{ij})$$

利用Hankel矩阵与矩阵乘积，令$U=Q^*H$，则

$$\tilde{H}_{i,j}= \sum_{k=1}^K Q_{i,k}U_{k,j}$$

对角平均则可化为

$$\begin{aligned} \sum_{j=j_1}^{j_m} \tilde{H}_{i-j+1,j} &=\sum_{k=1}^K\sum_{j=j_1}^{j_m}Q_{i-j+1,k}U_{k,j}\\ &=\sum_{k=1}^K\sum_{j=j_1}^{j_m}Q_{i,j}^{(k)}U_{j}^{(k)}\\ &=\sum_{k=1}^K \big(Q^{(k)}\cdot U^{(k)}\big)_i\\ \end{aligned}$$

其中$j_1=\max(i-M+1,1),j_m=\min(i,N)$，$Q^{(k)}$是一个Toeplitz矩阵，向量$U^{(k)}$满足$U_j^{(k)}=U_{k,j}$。$\big(Q^{(k)}\cdot U^{(k)}\big)$可使用快速算法计算矩阵乘积。

urQRd算法流程

小结

文章的核心是利用随机矩阵来做数据的降维，随机采样的原理可能需要看综述^[2]才能进一步了解，先mark下。另外，文章文献包含的文章^[3]和文章^[4]也是同类基于随机投影的矩阵近似算法。

References

---

1. Chiron L , Van Agthoven M A , Kieffer B , et al. Efficient denoising algorithms for large experimental datasets and their applications in Fourier transform ion cyclotron resonance mass spectrometry.[J]. Proceedings of the National Academy of Sciences of the United States of America, 2014, 111(4):1385-90. ↩︎

2. Halko N , Martinsson P G , Tropp J A . Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions[J]. Siam Review, 2010, 53(2):217-288. ↩︎

3. Woolfe F , Liberty E , Rokhlin V , et al. A fast randomized algorithm for the approximation of matrices[J]. Applied & Computational Harmonic Analysis, 2008, 25(3):335-366. ↩︎

4. Liberty E , Woolfe F , Martinsson P G , et al. Randomized algorithms for the low-rank approximation of matrices[J]. Proceedings of the National Academy of Sciences, 2008, 104(51):20167-20172. ↩︎