Vi studerar A-optimala design problem där vi ges vektorer v 1,. .., v n R d, ett heltal k ≥ d och målet är att välja en uppsättning S av k vektorer som minimerar spår av i.S v i v i −1. Traditionellt är problemet ett exempel på optimal design av experiment i statistik (Pubelsheim (2006)) där varje vektor motsvarar en linjär mätning av en okänd vektor och målet är att plocka k av dem som minimerar den genomsnittliga variansen av felet i den maximala sannolikheten uppskattningen av vektorn som mäts. Problemet är också att det finns applikationer inom sensorplacering i trådlösa nätverk (Joshi och Boyd (2009) (2013). I detta dokument introducerar vi proportionell volymprovtagning för att erhålla förbättrade approximationsalgoritmer för A-optimal design. Eftersom en matris, proportionell volym provtagning innebär att plocka en uppsättning kolumner S av storlek k med sannolikhet proportionell till μ(S) gånger det( i och med att v i v i ) för vissa mått μ. Vårt huvudsakliga resultat är att visa att det A-optimala designproblemet kan reduceras till ungefärliga självständighetsegenskaper hos måttet μ. Vi vädjar till hårddiskar som kandidatdistributioner μ som gör det möjligt för oss att få förbättrade approximationsalgoritmer för A-optimal design. Våra resultat inkluderar en d- approximation när k = d, en (1 + )- approximation när k =  ska d + 1 2 log 1 och k-d+1 - approximation när upprepningar av vektorer är tillåtna i lösningen. Vi överväger också generalisering av problemet för k ≤ d och få en k- approximation. Vi visar också att den proportionella volymprovtagningsalgoritmen ger approximationsalgoritmer för andra optimala designmål (såsom D-optimal design Singh och Xie (2018) och generaliserat kvotmål Mariet och Sra (2017)) som matchar eller förbättrar tidigare bäst kända resultat. Intressant nog visar vi att en liknande garanti inte kan erhållas för det e-optimala designproblemet. Vi visar också att A-optimal designproblem är NP-hård att approximera inom en fast konstant när k = d.
I REF föreslogs proportionell volymprovtagning för avrundningssteget och erhållna approximationsalgoritmer för klassisk A/D-optimalitet
Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}