Autonomous Toy Drone via Coresets for Pose Estimation

A coreset of a dataset is a small weighted set, such that querying the coreset provably yields a ([Formula: see text])-factor approximation to the original (full) dataset, for a given family of queries. This paper suggests accurate coresets ([Formula: see text]) that are subsets of the input for fundamental optimization problems. These coresets enabled us to implement a “Guardian Angel” system that computes pose-estimation in a rate [Formula: see text] frames per second. It tracks a toy quadcopter which guides guests in a supermarket, hospital, mall, airport, and so on. We prove that any set of n matrices in [Formula: see text] whose sum is a matrix S of rank r, has a coreset whose sum has the same left and right singular vectors as S, and consists of [Formula: see text] matrices, independent of n. This implies the first (exact, weighted subset) coreset of [Formula: see text] points to problems such as linear regression, PCA/SVD, and Wahba’s problem, with corresponding streaming, dynamic, and distributed versions. Our main tool is a novel usage of the Caratheodory Theorem for coresets, an algorithm that computes its set in time that is linear in its cardinality. Extensive experimental results on both synthetic and real data, companion video of our system, and open code are provided.