Vi inleder studiet av glesa återhämtningsproblem under Earth-Mover Distance (EMD). Specifikt, vi designar en distribution över m × n matriser A sådan att för alla x, givet Ax, kan vi återställa en k-sparse approximation till x under EMD avstånd. En konstruktion ger m = O(k log (n/k)) och en 1 + approximationsfaktor, som motsvarar den bästa möjliga gränsen för andra felmått, såsom 1 norm. Våra algoritmer erhålls genom att utnyttja nya anslutningar till andra problem och områden, såsom strömmande algoritmer för k-mediankluster och modellbaserad kompressiv avkänning. Vi tillhandahåller även nya algoritmer och resultat för de senare problemen.
Indyk & Price REF studerade problemet med sparsam återhämtning under Earth Mover Distance.
K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance
{'venue': "STOC '11", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}