Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding

Matrix reconstruction is a fundamental problem in high-dimensional data analysis and video background modeling. Robust principal component analysis (RPCA) decomposes an observed data matrix into a low-rank background component and a sparse component representing foreground objects or corruption. However, solvers based on the augmented Lagrangian method (ALM) and its linearized variant (LALM) repeatedly invoke singular value decomposition (SVD), which is computationally expensive for video-scale matrices. This study develops a noise-aware randomized LALM framework that combines randomized linear-time approximate SVD, adaptive regularization based on normalized data dispersion, and dynamic rank estimation. The framework is evaluated using synthetic SVD approximation, singular value thresholding (SVT) preservation, and background reconstruction on 14 Scene Background Initialization (SBI) sequences, with ten random-seed runs per sequence–method pair. Additional statistical, parameter-sensitivity, cross-dataset, and ablation analyses are conducted to assess robustness and the contributions of the adaptive components. The randomized approximate SVD achieves an average 40.52× speedup over full SVD. In the SVT experiments, sampling 80 columns provides a practical efficiency–accuracy balance. On SBI, the proposed method achieves an average peak signal-to-noise ratio (PSNR) of 26.61 dB, signal-to-noise ratio (SNR) of 21.54 dB, and elapsed time of 57.90 s while obtaining the lowest average gray-level error (AGE), percentage of error pixels (pEPs), and percentage of clustered error pixels (pCEPs) among the tested LALM variants. The additional analyses indicate that the performance gains are scene dependent and that dynamic rank estimation and noise-aware regularization provide complementary benefits. Overall, the proposed framework offers a practical quality–efficiency trade-off for RPCA-based video background reconstruction.

Authors

Institutions

Publication Details

Journal
Algorithms
Published
2026-11-17
DOI
https://doi.org/10.3390/a19111009
Primary Topic
Sparse and Compressive Sensing Techniques
Type
article
Field-Weighted Citation Impact
0.00
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding

Na Zhou, Wentao Wang
1 links
Algorithms
Sparse and Compressive Sensing Techniques
article

Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding

Na Zhou, Wentao Wang
article en

Abstract

Matrix reconstruction is a fundamental problem in high-dimensional data analysis and video background modeling. Robust principal component analysis (RPCA) decomposes an observed data matrix into a low-rank background component and a sparse component representing foreground objects or corruption. However, solvers based on the augmented Lagrangian method (ALM) and its linearized variant (LALM) repeatedly invoke singular value decomposition (SVD), which is computationally expensive for video-scale matrices. This study develops a noise-aware randomized LALM framework that combines randomized linear-time approximate SVD, adaptive regularization based on normalized data dispersion, and dynamic rank estimation. The framework is evaluated using synthetic SVD approximation, singular value thresholding (SVT) preservation, and background reconstruction on 14 Scene Background Initialization (SBI) sequences, with ten random-seed runs per sequence–method pair. Additional statistical, parameter-sensitivity, cross-dataset, and ablation analyses are conducted to assess robustness and the contributions of the adaptive components. The randomized approximate SVD achieves an average 40.52× speedup over full SVD. In the SVT experiments, sampling 80 columns provides a practical efficiency–accuracy balance. On SBI, the proposed method achieves an average peak signal-to-noise ratio (PSNR) of 26.61 dB, signal-to-noise ratio (SNR) of 21.54 dB, and elapsed time of 57.90 s while obtaining the lowest average gray-level error (AGE), percentage of error pixels (pEPs), and percentage of clustered error pixels (pCEPs) among the tested LALM variants. The additional analyses indicate that the performance gains are scene dependent and that dynamic rank estimation and noise-aware regularization provide complementary benefits. Overall, the proposed framework offers a practical quality–efficiency trade-off for RPCA-based video background reconstruction.

AlgorithmsVol. 19(11)
Nanjing University of Science and Technology (CN), ZTE (China) (CN), Nanjing University of Science and Technology ZiJin College (CN)
Sparse and Compressive Sensing Techniques
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon