Subrymdens approximationsproblem Subspace(k, p) ber om ett k-dimensionellt linjärt subutrymme som passar en given uppsättning m-punkter i R n optimalt. Felet för montering är en generalisering av de minst kvadraterna passar och använder p-normen för de avstånd ( 2 avstånd) av punkterna från subrymden, t.ex. p = ❌ innebär att minimera 2 avstånd av den längst bort punkten från subrymden. Tidigare arbete om approximering av subrymden beaktar antingen fallet med små eller konstant k och p [27, 11, 14] eller fallet p = ∞ [16, 8, 17, 7, 24, 23, 29]. I detta papper studerar vi algoritmer och hårdhet för Subspace(k, p) i det naturliga intervallet 1 ≤ k ≤ n och 2 ≤ p ≤ ∞. Våra resultat är som följer. • Utöka konvex avslappning och avrundning tekniker av Varadarajan, Venkatesh, Ye och Zhang [29], ger vi en polynom tid approximation algoritm för Subspace(k, p), för alla k och alla p ≥ 2, med en approximation garanti på ungefär 2γ p, där γ p / e (1 + o 1) är p th moment av en standard normalvariabel. Detta förbättrar till γ p för k = n − 1. • Vi uppvisar en enkel integrality gap (eller "rank gap") exempel för vår konvex avkoppling ger ett gap av γ p (1 - ε), för alla konstant ε > 0. • Vi visar att, förutsatt att den unika Games Conjecture, subrymd approximation problemet är svårt att approximera inom en faktor som är bättre än γ p (1 - ε), för alla konstant ε > 0. Vår hårdhet minskning innebär en diktatur test som skiljer sig något från "lång kod" baserade tester som används i minskningar från unika spel, och verkar bättre lämpad för problem av en kontinuerlig natur.
Till exempel, REF studera en konvex relation, och en avrundning algoritm för att lösa subrymd approximation problem (en p generalisering av de minst kvadrater passar), som är relaterad till men skiljer sig från vårt problem.
Algorithms and hardness for subspace approximation
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}