Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Aug:2023:390-401.
doi: 10.1145/3580305.3599361. Epub 2023 Aug 4.

Generalized Matrix Local Low Rank Representation by Random Projection and Submatrix Propagation

Pengtao Dang  1 , Haiqi Zhu  2 , Tingbo Guo  3 , Changlin Wan  4 , Tong Zhao  5 , Paul Salama  1 , Yijie Wang  2 , Sha Cao  3 , Chi Zhang  3
Affiliations

Generalized Matrix Local Low Rank Representation by Random Projection and Submatrix Propagation

Pengtao Dang et al. KDD. 2023 Aug.

Abstract

Matrix low rank approximation is an effective method to reduce or eliminate the statistical redundancy of its components. Compared with the traditional global low rank methods such as singular value decomposition (SVD), local low rank approximation methods are more advantageous to uncover interpretable data structures when clear duality exists between the rows and columns of the matrix. Local low rank approximation is equivalent to low rank submatrix detection. Unfortunately, existing local low rank approximation methods can detect only submatrices of specific mean structure, which may miss a substantial amount of true and interesting patterns. In this work, we develop a novel matrix computational framework called RPSP (Random Probing based submatrix Propagation) that provides an effective solution for the general matrix local low rank representation problem. RPSP detects local low rank patterns that grow from small submatrices of low rank property, which are determined by a random projection approach. RPSP is supported by theories of random projection. Experiments on synthetic data demonstrate that RPSP outperforms all state-of-the-art methods, with the capacity to robustly and correctly identify the low rank matrices when the pattern has a similar mean as the background, background noise is heteroscedastic and multiple patterns present in the data. On real-world datasets, RPSP also demonstrates its effectiveness in identifying interpretable local low rank matrices.

Keywords: Computing methodologies→Machine learning algorithms; Local low rank matrix; Random projection; Randomized matrix approximation; Representation learning; Sub-matrix detection.

PubMed Disclaimer

Figures

Figure 1:
Figure 1:
One example of the Matrix Local Low Rank Representation (MLLRR) Problem.
Figure 2:
Figure 2:
Mathematical considerations of random projection-based singular value computation.
Figure 3:
Figure 3:
The framework of the RPSP algorithm.
Figure 4:
Figure 4:
Benchmark of RPSP on Synthetic Data.
Figure 5:
Figure 5:
Experiment on real-world data.
See this image and copyright information in PMC

References

    1. Achlioptas Dimitris. 2003. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Journal of computer and System Sciences 66, 4 (2003), 671–687
    1. Banerjee Arindam, Dhillon Inderjit, Ghosh Joydeep, Merugu Srujana, and Modha Dharmendra S. 2007. A generalized maximum entropy approach to bregman co-clustering and matrix approximation. Journal of Machine Learning Research 8, Aug (2007), 1919–1986.
    1. Bingham Ella and Mannila Heikki. 2001. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining.
    1. Bouwmans Thierry and Zahzah El Hadi. 2014. Robust PCA via principal component pursuit: A review for a comparative evaluation in video surveillance. Computer Vision and Image Understanding 122 (2014), 22–34.
    1. Chang Wennan, Wan Changlin, Zang Yong, Zhang Chi, and Cao Sha. 2020. Supervised clustering of high dimensional data using regularized mixture modeling. arXiv preprint arXiv:2007.09720 (2020). - PMC - PubMed