English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper studies the problem of deterministic rank-one matrix completion.It is known that the simplest semidefinite programming relaxation, involvingminimization of the nuclear norm, does not in general return the solution forthis problem. In this paper, we show that in every instance where the problemhas a unique solution, one can provably recover the original matrix through tworounds of semidefinite programming relaxation with minimization of the tracenorm. We further show that the solution of the proposed semidefinite program isLipschitz-stable with respect to perturbations of the observed entries, unlikemore basic algorithms such as nonlinear propagation or ridge regression. Ourproof is based on recursively building a certificate of optimalitycorresponding to a dual sum-of-squares (SOS) polynomial. This SOS polynomial isbuilt from the polynomial ideal generated by the completion constraints and themonomials provided by the minimization of the trace. The proposed relaxationfits in the framework of the Lasserre hierarchy, albeit with the key additionof the trace objective function. We further show how to represent andmanipulate the moment tensor in favorable complexity by means of a hierarchicallow-rank decomposition.

Stable rank one matrix completion is solved by two rounds of semidefinite programming relaxation