Loading...
Please wait, while we are loading the content...
Similar Documents
Low-Rank Matrix Completion 1 using 2 Nuclear Norm Minimization
| Content Provider | Semantic Scholar |
|---|---|
| Author | Huang, Shimeng Wolkowicz, Henry |
| Copyright Year | 2017 |
| Abstract | 8 Minimization of the nuclear norm, NNM, is often used as a surrogate (convex relaxation) 9 for finding the minimum rank completion (recovery) of a partial matrix. The minimum nuclear 10 norm problem can be solved as a trace minimization semidefinite programming problem, SDP. 11 Interior point algorithms are the current methods of choice for this class of problems. This 12 means that it is difficult to: solve large scale problems; exploit sparsity; and get high accuracy 13 solutions. 14 The SDP and its dual are regular in the sense that they both satisfy strict feasibility. In 15 this paper we take advantage of the structure at optimality for the NNM. We show that even 16 though strict feasibility holds, the facial reduction framework used for problems where strict 17 feasibility fails can be successfully applied to obtain a proper face that contains the optimal 18 set. This can dramatically reduce the size of the final NNM problem, while simultaneously 19 guaranteeing a low-rank solution. This can be compared to identifying the active set in general 20 nonlinear programming problems. 21 We include numerical tests for both exact and noisy cases. 22 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.math.uwaterloo.ca/~hwolkowi/henry/reports/Rev2facredpsdcompl.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
