Vi studerar problemet med att välja en delmängd av k slumpvariabler från en stor uppsättning, för att få den bästa linjära förutsägelsen av en annan variabel av intresse. Detta problem kan ses mot bakgrund av både urval av funktioner och gles approximation. Vi analyserar prestandan hos allmänt använda giriga heuristiker, med hjälp av insikter från maximeringen av submodulära funktioner och spektralanalys. Vi introducerar submodularitetsförhållandet som en nyckelkvantitet för att hjälpa till att förstå varför giriga algoritmer fungerar bra även när variablerna är högt korrelerade. Med hjälp av våra tekniker får vi de starkaste kända approximationsgarantierna för detta problem, både när det gäller submodularitetsförhållandet och det minsta k-sparse eigenvärdet av kovariansmatrisen. Vi demonstrerar vidare den breda tillämpligheten av våra tekniker genom att analysera giriga algoritmer för ordlistans urvalsproblem, och avsevärt förbättra de tidigare kända garantierna. Vår teoretiska analys kompletteras med experiment på verkliga och syntetiska datamängder; experimenten visar att submodularitetsförhållandet är en starkare prediktor för giriga algoritmers prestanda än andra spektralparametrar.
REF introducerade submodularitetsförhållandet och visade att den giriga standardalgoritmen har ett förhållande på 1 − e −γ.
Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}