Convergence Analysis and Bilevel Optimization Algorithms for Matrix Completion Problems
| dc.creator | Mahendra Panagoda | |
| dc.date.accessioned | 2022-01-25T19:47:06Z | |
| dc.date.available | 2022-01-25T19:47:06Z | |
| dc.date.issued | 2021 | |
| dc.description.abstract | The soft SVD is a robust matrix decomposition algorithm and a key component of matrix completion methods. However, computing the soft SVD for large sparse matrices is often impractical using conventional numerical methods for the SVD due to large memory requirements. The Rank-Restricted Soft SVD (RRSS) algorithm introduced by Hastie et al. addressed this issue by sequentially computing low-rank SVDs that easily fit in memory. We analyze the convergence of the standard RRSS algorithm and we give examples where the standard algorithm does not converge. We show that convergence requires a modification of the standard algorithm, and is related to non-uniqueness of the SVD. Our modification specifies a consistent choice of sign for the left singular vectors of the low-rank SVDs in the iteration. Under these conditions, we prove linear convergence of the singular vectors using a technique motivated by alternating subspace iteration. We then derive a fixed point iteration for the evolution of the singular values and show linear convergence to the soft thresholded singular values of the original matrix. This last step requires a perturbation result for fixed point iterations which may be of independent interest. Next, we design a bilevel optimization scheme to find the optimal regularization parameters. Several examples, including image reconstruction, are provided which illustrate the efficacy of the approach.Our results above have wider applications in an array of optimization and matrix decomposition problems. These include optimization problems using alternative direction method and high dimensional matrix decomposition algorithms. In many practical situations, the original matrix is relatively large and not fully dense, and matrix decomposition via a simple SVD approach is not possible. Establishing the convergence of the soft thresholding algorithm guarantees the numerical stability of the scheme. | |
| dc.identifier.uri | https://hdl.handle.net/1920/12667 | |
| dc.title | Convergence Analysis and Bilevel Optimization Algorithms for Matrix Completion Problems | |
| thesis.degree.discipline | Mathematics | |
| thesis.degree.grantor | George Mason University | |
| thesis.degree.level | Ph.D. |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Panagoda_gmu_0883E_12625.pdf
- Size:
- 9.18 MB
- Format:
- Adobe Portable Document Format