Rank-one matrix completion is solved by the sum-of-squares relaxation of order two
This note studies the problem of nonsymmetric rank-one matrix completion. We show that in every instance where the problem has a unique solution, one can recover the original matrix through the second round of the sum-of-squares/Lasserre hierarchy with minimization of the trace of the moments matrix...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110289 https://orcid.org/0000-0001-7052-5097 |
| _version_ | 1811069733890424832 |
|---|---|
| author | Cosse, Augustin Demanet, Laurent |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Cosse, Augustin Demanet, Laurent |
| author_sort | Cosse, Augustin |
| collection | MIT |
| description | This note studies the problem of nonsymmetric rank-one matrix completion. We show that in every instance where the problem has a unique solution, one can recover the original matrix through the second round of the sum-of-squares/Lasserre hierarchy with minimization of the trace of the moments matrix. Our proof system is based on iteratively building a sum of N - 1 linearly independent squares, where N is the number of monomials of degree at most two, corresponding to the canonical basis (z[superscript α] - z[subscript 0][superscript α])[superscript 2]. Those squares are constructed from the ideal I generated by the constraints and the monomials provided by the minimization of the trace. |
| first_indexed | 2024-09-23T08:15:05Z |
| format | Article |
| id | mit-1721.1/110289 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:15:05Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1102892022-09-23T11:56:01Z Rank-one matrix completion is solved by the sum-of-squares relaxation of order two Cosse, Augustin Demanet, Laurent Massachusetts Institute of Technology. Department of Mathematics Demanet, Laurent This note studies the problem of nonsymmetric rank-one matrix completion. We show that in every instance where the problem has a unique solution, one can recover the original matrix through the second round of the sum-of-squares/Lasserre hierarchy with minimization of the trace of the moments matrix. Our proof system is based on iteratively building a sum of N - 1 linearly independent squares, where N is the number of monomials of degree at most two, corresponding to the canonical basis (z[superscript α] - z[subscript 0][superscript α])[superscript 2]. Those squares are constructed from the ideal I generated by the constraints and the monomials provided by the minimization of the trace. United States. Office of Naval Research National Science Foundation (U.S.) TOTAL (Firm) 2017-06-26T23:18:45Z 2017-06-26T23:18:45Z 2016-01 Article http://purl.org/eprint/type/ConferencePaper 978-1-4799-1963-5 http://hdl.handle.net/1721.1/110289 Cosse, Augustin, and Laurent Demanet. “Rank-One Matrix Completion Is Solved by the Sum-of-Squares Relaxation of Order Two.” 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) (December 2015). ©2015 IEEE https://orcid.org/0000-0001-7052-5097 en_US http://dx.doi.org/10.1109/CAMSAP.2015.7383723 2015 IEEE 6th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Cosse, Augustin Demanet, Laurent Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title | Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title_full | Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title_fullStr | Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title_full_unstemmed | Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title_short | Rank-one matrix completion is solved by the sum-of-squares relaxation of order two |
| title_sort | rank one matrix completion is solved by the sum of squares relaxation of order two |
| url | http://hdl.handle.net/1721.1/110289 https://orcid.org/0000-0001-7052-5097 |
| work_keys_str_mv | AT cosseaugustin rankonematrixcompletionissolvedbythesumofsquaresrelaxationofordertwo AT demanetlaurent rankonematrixcompletionissolvedbythesumofsquaresrelaxationofordertwo |