Learning Approach For Fast Approximate Matrix Factorizations
Learning Approach For Fast Approximate Matrix Factorizations
复制标题
DOI：
10.1109/icassp43922.2022.9747165
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Haiyan Yu;Zhen Qin;Zhihui Zhu
中科院分区：
文献类型：
--
作者：
Haiyan Yu;Zhen Qin;Zhihui Zhu
有效地计算输入数据X的（近似）标准正交基和低秩近似在数据分析中起着至关重要的作用。对于这样的任务，最有效的算法之一是随机化算法，其通过用尺寸小得多的随机草绘矩阵A计算投影XA，然后计算标准正交基以及高矩阵XA的低秩因子分解来进行。虽然随机矩阵A是事实上的选择，但在这项工作中，我们通过利用学习方法从一组训练数据中找到自适应草图矩阵A来提高其性能。我们推导出一个封闭形式的配方的梯度的训练问题，使我们能够使用有效的基于梯度的算法。我们还扩展了这种方法，学习结构化的草图矩阵，如稀疏草图矩阵，从输入数据中选择几个有代表性的列。我们对合成数据和真实的数据的实验表明，无论是学习密集和稀疏素描矩阵优于随机的，在寻找近似正交基和低秩近似。
Efficiently computing an (approximate) orthonormal basis and low-rank approximation for the input data X plays a crucial role in data analysis. One of the most efficient algorithms for such tasks is the randomized algorithm, which proceeds by computing a projection XA with a random sketching matrix A of much smaller size, and then computing the orthonormal basis as well as low-rank factorizations of the tall matrix XA. While a random matrix A is the de facto choice, in this work, we improve upon its performance by utilizing a learning approach to find an adaptive sketching matrix A from a set of training data. We derive a closed-form formulation for the gradient of the training problem, enabling us to use efficient gradient-based algorithms. We also extend this approach for learning structured sketching matrix, such as the sparse sketching matrix that performs as selecting a few number of representative columns from the input data. Our experiments on both synthetical and real data show that both learned dense and sparse sketching matrices outperform the random ones in finding the approximate orthonormal basis and low-rank approximations.