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.| 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
https://hdl.handle.net/20.500.12608/115733