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.
Som ett exempel, Deshpande et al REF gav en O (p p/2 ) approximation algoritm för problemet med att hitta en subrymd som minimerar summan av p avstånd till datapunkterna (för p > 2).
Algorithms and hardness for subspace approximation
{'venue': "SODA '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}