Sketches by MoSSaRT: Representative selection from manifolds with gross sparse corruptions

• Published in: Pattern recognition 2022-04, Vol.124, p.108454, Article 108454
• Main Authors: Sedghi, Mahlagha, Georgiopoulos, Michael, Atia, George K.
• Format: Article
• Language: English
• Subjects: Gross sparse corruption; Manifold learning; Representative selection; Reproducing kernel Hilbert spaces
• ISSN: 0031-3203; 1873-5142
• DOI: 10.1016/j.patcog.2021.108454

•A reproduction profile encodes the data relations of grossly corrupted manifold structures.•Approximate feature maps emulate a desired feature mapping associated with a RKHS.•Scalable and parallelizable ADMM-based algorithm has nearly linear complexity in the data size.•The proxy objective function induced by the approximate features converges exponentially fast.•The representatives are vertices of the symmetrized convex hull of the data in a transformed space. Conventional sampling techniques fall short of selecting representatives that encode the underlying conformation of non-linear manifolds. The problem is exacerbated if the data is contaminated with gross sparse corruptions. In this paper, we present a data selection approach, dubbed MoSSaRT, which draws robust and descriptive sketches of grossly corrupted manifold structures. Built upon an explicit randomized transformation, we obtain a judiciously designed representation of the data relations, which facilitates a versatile selection approach accounting for robustness to gross corruption, descriptiveness and novelty of the chosen representatives, simultaneously. Our model lends itself to a convex formulation with an efficient parallelizable algorithm, which coupled with our randomized matrix structures gives rise to a highly scalable implementation. Theoretical analysis guarantees probabilistic convergence of the approximate function to the desired objective function and reveals insightful geometrical characterization of the chosen representatives. Finally, MoSSaRT substantially outperforms the state-of-the-art algorithms as demonstrated by experiments conducted on both real and synthetic data.