Abstrakt. Antag att vi får en matris som bildas genom att lägga till en okänd gles matris till en okänd låg-rank matris. Vårt mål är att bryta ner den givna matrisen i dess sparsamma och lågvärdiga komponenter. Ett sådant problem uppstår i ett antal tillämpningar i modell- och systemidentifiering, och är NP-hård i allmänhet. I detta papper anser vi att en konvex optimering formulering att dela upp den angivna matrisen i dess komponenter, genom att minimera en linjär kombination av 1 norm och den nukleära normen av komponenterna. Vi utvecklar ett begrepp om osammanhängande rankning, uttryckt som en osäkerhetsprincip mellan ett matrismönster och dess rad- och kolumnrymder, och använder det för att karakterisera både grundläggande identifiability och (deterministiska) tillräckligt villkor för exakt återhämtning. Vår analys är geometrisk i naturen, med tangenten utrymmen till algebraiska sorter av glesa och låg-rankade matriser spelar en framträdande roll. När de sparsamma och lågvärdiga matriserna hämtas från vissa naturliga slumpmässiga ensembler visar vi att de tillräckliga förutsättningarna för exakt återhämtning är uppfyllda med stor sannolikhet. Vi avslutar med simuleringsresultat på syntetiska matris sönderdelningsproblem. Nyckelord. matris nedbrytning, konvex avslappning, 1 norm minimering, nukleär norm minimering, osäkerhet princip, semidefinit programmering, rang, gleshet AMS ämnesklassificeringar. 90C25; 90C22; 90C59; 93B30 1. Inledning. Komplexa system och modeller uppstår i en mängd olika problem inom vetenskap och teknik. I många tillämpningar består sådana komplexa system och modeller ofta av flera enklare system och modeller. Därför, för att bättre förstå beteendet och egenskaperna hos ett komplext system en naturlig strategi är att bryta systemet i dess enklare komponenter. I detta papper överväger vi matris representationer av system och statistiska modeller där våra matriser bildas genom att lägga samman glesa och låg-rankade matriser. Vi studerar problemet med att återvinna de glesa och låg-ranka komponenter som inte gett någon förkunskaper om gleshetsmönstret i gles matris, eller rangen av låg-rank matris. Vi föreslår ett dragbart konvext program för att återställa dessa komponenter, och ger tillräckliga villkor under vilka vår procedur återvinner de glesa och låg-rankade matriser exakt. Ett sådant nedbrytningsproblem uppstår i ett antal inställningar, där de sparsamma och lågrankade matriserna har olika tolkningar beroende på applikationen. I en statistisk modellvalsinställning kan den glesa matrisen motsvara en Gaussisk grafisk modell [18] och den lågrankade matrisen kan sammanfatta effekten av latenta, oobserverade variabler. Att bryta ner en viss modell i dessa enklare komponenter är användbart för att utveckla effektiva skattnings- och slutalgoritmer. Vid beräkningskomplexitet fångar begreppet matrisstelhet [27] det minsta antal poster i en matris som måste ändras för att minska matrisens rang under en angiven nivå (ändringarna kan vara av godtycklig omfattning). Gränser för stelheten hos
Vårt arbete följer noga det av Chandrasekaran et al. REF, som initierade studien av rank-parsitet inkoherens och dess tillämpning på matris sönderdelningar.
Rank-Sparsity Incoherence for Matrix Decomposition
{'venue': 'SIAM Journal on Optimization, Vol. 21, Issue 2, pp. 572-596, 2011', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}