Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding
Algorithms · 17.11.2026 · 19 (11) · 1009
DOI: 10.3390/a19111009 ↗Kurz gefasst
Fachartikel in der Zeitschrift Algorithms, online erschienen am 17.11.2026. Verfasst von Na Zhou und 1 weiteren Autor:innen. Die Arbeit nennt 16 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
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.
Zitieren
APA
Zhou, N., & Wang, W. (2026). Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding. Algorithms, 19(11), 1009. https://doi.org/10.3390/a19111009
Vancouver
Zhou N, Wang W. Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding. Algorithms. 2026;19(11):1009. doi:10.3390/a19111009
BibTeX
@article{Zhou2026,
author = {Zhou, Na and Wang, Wentao},
title = {Efficient Matrix Reconstruction via Randomized Linear-Time Singular Value Decomposition and Adaptive Thresholding},
journal = {Algorithms},
year = {2026},
volume = {19},
number = {11},
pages = {1009},
doi = {10.3390/a19111009}
}
EUVIMED