Matrix completion is a powerful technique used to reconstruct an entire high-dimensional matrix from highly incomplete, local information. This thesis establishes that, when dealing with a low-rank matrix, this reconstruction is possible, as the expected average error per entry can be proven to be much smaller than the maximal magnitude of an entry. Specifically, we show that exact recovery is guaranteed once the number of shown entries exceeds a logarithmic margin. To this end, we model the revealed data as a random sampling process where each entry is observed independently with a given probability, and we combine probabilistic symmetrization with Matrix Bernstein Inequality to obtain the desired bound.

Matrix Completion for Low-Rank Matrices

ZARDO, ALICE
2025/2026

Abstract

Matrix completion is a powerful technique used to reconstruct an entire high-dimensional matrix from highly incomplete, local information. This thesis establishes that, when dealing with a low-rank matrix, this reconstruction is possible, as the expected average error per entry can be proven to be much smaller than the maximal magnitude of an entry. Specifically, we show that exact recovery is guaranteed once the number of shown entries exceeds a logarithmic margin. To this end, we model the revealed data as a random sampling process where each entry is observed independently with a given probability, and we combine probabilistic symmetrization with Matrix Bernstein Inequality to obtain the desired bound.
2025
Matrix Completion for Low-Rank Matrices
Matrix Completion
SVD
Concentration Bounds
File in questo prodotto:
File Dimensione Formato  
Thesis - Alice Zardo.pdf

accesso aperto

Dimensione 955.04 kB
Formato Adobe PDF
955.04 kB Adobe PDF Visualizza/Apri

The text of this website © Università degli studi di Padova. Full Text are published under a non-exclusive license. Metadata are under a CC0 License

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.12608/115733