Gradminimeringsproblemet är att hitta den lägsta rank matrisen i en given uppsättning. Kärnnormminimering har föreslagits som en konvex avslappning av rangminimering. Recht, Fazel och Parrilo har visat att atomnormminimering som är föremål för en affin restriktion är likvärdig med rangminimering under ett visst villkor givet i termer av den rank-begränsade isometry egenskapen. I närvaro av mätbuller, eller med endast ungefärlig generativ modell med låg rankning, är den lämpliga restriktionen en ellipsoid snarare än ett affin utrymme. Det finns polynom-tid algoritmer för att lösa den nukleära normminimering med en ellipsoidal begränsning, men ingen prestandagaranti har visats för dessa algoritmer. I detta dokument härleder vi en sådan uttrycklig prestandagaranti, som begränsar felet i den ungefärliga lösning som tillhandahålls av kärnnormminimering med en ellipsoidal begränsning.
Matrix avkänning har först bevisats i konvex inställning med hjälp av nukleär norm minimization [37, 41, REF.
Guaranteed Minimum Rank Approximation from Linear Observations by Nuclear Norm Minimization with an Ellipsoidal Constraint
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}