Efficient and Adaptive CUR Matrix Decomposition for Flexible Compression of Network Monitoring Data

Network-wide monitoring is indispensable for a variety of network applications. However, as network sizes increase and the demand for fine-grained, continuous measurements grows, the challenges associated with storing and transmitting such data intensify. Recent studies have shown that network-wide monitoring data exhibits a low-rank structure, which can be exploited using matrix decomposition techniques for compression. This paper presents a compression algorithm for low-rank matrices based on CUR decomposition, which offers enhanced interpretability compared to SVD-based compression. Existing CUR solutions, however, lack the capability for fast and flexible compression that can dynamically adjust to matrix size requirements while preserving maximal approximation accuracy. We address the challenges associated with CUR row and column selection by formulating it as a deterministic CUR matrix decomposition problem, involving a selection matrix <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{W}$</tex-math></inline-formula>. To achieve rapid compression, we propose an algorithm that effectively accelerates the process of solving for the parameter matrix <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{W}$</tex-math></inline-formula>. Our approach reveals that the vectors in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{W}$</tex-math></inline-formula> indicate the importance of each row and column in forming the respective row and column subspaces. Leveraging this insight, we develop a flexible compression algorithm based on the sorted vectors in the selection matrix <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathbf{W}$</tex-math></inline-formula>. This method not only ensures the required compression ratio but also maintains maximal approximation accuracy. Extensive experiments on both synthesized and real data demonstrate that our algorithm can deliver fast and precise matrix compression, aligning with the desired compression ratio.