MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data
This addresses the pervasive challenge of aligning large datasets across domains, such as in single cell molecular data, but appears incremental as it builds on existing black box matching procedures.
The authors tackled the problem of comparing and aligning large datasets by introducing MREC, a recursive decomposition algorithm that partitions data, matches partitions, and recursively matches points within them, enabling application to extremely large datasets with demonstrated flexibility in single cell molecular data analysis.
Comparing and aligning large datasets is a pervasive problem occurring across many different knowledge domains. We introduce and study MREC, a recursive decomposition algorithm for computing matchings between data sets. The basic idea is to partition the data, match the partitions, and then recursively match the points within each pair of identified partitions. The matching itself is done using black box matching procedures that are too expensive to run on the entire data set. Using an absolute measure of the quality of a matching, the framework supports optimization over parameters including partitioning procedures and matching algorithms. By design, MREC can be applied to extremely large data sets. We analyze the procedure to describe when we can expect it to work well and demonstrate its flexibility and power by applying it to a number of alignment problems arising in the analysis of single cell molecular data.