Surgical Planning Laboratory - Brigham & Women's Hospital - Boston, Massachusetts USA - a teaching affiliate of Harvard Medical School

Surgical Planning Laboratory

The Publication Database hosted by SPL

All Publications | Upload | Advanced Search | Gallery View | Download Statistics | Help | Import | Log in

Sampling from Determinantal Point Processes for Scalable Manifold Learning

Institution:
Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA.
Publisher:
IPMI 2015
Publication Date:
Jun-2015
Journal:
Inf Process Med Imaging
Volume Number:
24
Pages:
687-98
Citation:
Inf Process Med Imaging. 2015 Jun;24:687-98.
PubMed ID:
26221713
PMCID:
PMC4524741
Appears in Collections:
NAC, NA-MIC
Sponsors:
P41 EB015902/EB/NIBIB NIH HHS/United States
U54 EB005149/EB/NIBIB NIH HHS/United States
Generated Citation:
Wachinger C., Golland P. Sampling from Determinantal Point Processes for Scalable Manifold Learning. Inf Process Med Imaging. 2015 Jun;24:687-98. PMID: 26221713. PMCID: PMC4524741.
Downloaded: 979 times. [view map]
Paper: Download, View online
Export citation:
Google Scholar: link

High computational costs of manifold learning prohibit its application for large datasets. A common strategy to overcome this problem is to perform dimensionality reduction on selected landmarks and to successively embed the entire dataset with the Nyström method. The two main challenges that arise are: (i) the landmarks selected in non-Euclidean geometries must result in a low reconstruction error, (ii) the graph constructed from sparsely sampled landmarks must approximate the manifold well. We propose to sample the landmarks from determinantal distributions on non-Euclidean spaces. Since current determinantal sampling algorithms have the same complexity as those for manifold learning, we present an efficient approximation with linear complexity. Further, we recover the local geometry after the sparsification by assigning each landmark a local covariance matrix, estimated from the original point set. The resulting neighborhood selection based on the Bhattacharyya distance improves the embedding of sparsely sampled manifolds. Our experiments show a significant performance improvement compared to state-of-the-art landmark selection techniques on synthetic and medical data.

Additional Material
1 File (61.557kB)
Wachinger-IPMI2015-fig2.jpg (61.557kB)