A large number of algorithms in machine learning, from principal component analysis (PCA), and its non-linear (kernel) extensions, to more recent spectral embedding and support estimation methods, rely on estimating a linear subspace from samples. In this paper we introduce a general formulation of this problem and derive novel learning error estimates. Our results rely on natural assumptions on the spectral properties of the covariance operator associated to the data distribution, and hold for a wide class of metrics between subspaces. As special cases, we discuss sharp error estimates for the reconstruction properties of PCA and spectral support estimation. Key to our analysis is an operator theoretic approach that has broad applicability to spectral learning methods.

Given an anisotropic Voronoi diagram, we address the fundamental question of when its dual is embedded. We show that, by requiring only that the primal be orphan-free (have connected Voronoi regions), its dual is always guaranteed to be an embedded triangulation. Further, the primal diagram and its dual have properties that parallel those of ordinary Voronoi diagrams: the primal's vertices, edges, and faces are connected, and the dual triangulation has a simple, closed boundary. Additionally, if the underlying metric has bounded anisotropy (ratio of eigenvalues), the dual is guaranteed to triangulate the convex hull of the sites. These results apply to the duals of anisotropic Voronoi diagrams of any set of sites, so long as their Voronoi diagram is orphan-free. By combining this general result with existing conditions for obtaining orphan-free anisotropic Voronoi diagrams, a simple and natural condition for a set of sites to form an embedded anisotropic Delaunay triangulation follows.

We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-flats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-flats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-flats, both the results and the mathematical tools are new.

We study the problem of estimating, in the sense of optimal transport metrics, a measure which is assumed supported on a manifold embedded in a Hilbert space. By establishing a precise connection between optimal transport metrics, optimal quantization, and learning theory, we derive new probabilistic bounds for the performance of a classic algorithm in unsupervised learning (k-means), when used to produce a probability measure derived from the data. In the course of the analysis, we arrive at new lower bounds, as well as probabilistic bounds on the convergence rate of the empirical law of large numbers, which, unlike existing bounds, are applicable to a wide class of measures.

When a curved mirror-like surface moves relative to its environment, it induces a motion field-or specular flow- on the image plane that observes it. This specular flow is related to the mirror's shape through a non-linear partial differential equation, and there is interest in understanding when and how this equation can be solved for surface shape. Existing analyses of this `shape from specular flow equation' have focused on closed-form solutions, and while they have yielded insight, their critical reliance on externally-provided initial conditions and/or specific motions makes them difficult to apply in practice. This paper resolves these issues. We show that a suitable reparameterization leads to a linear formulation of the shape from specular flow equation. This formulation radically simplifies the reconstruction process and allows, for example, both motion and shape to be recovered from as few as two specular flows even when no externally-provided initial conditions are available. Our analysis moves us closer to a practical method for recovering shape from specular flow that operates under arbitrary, unknown motions in unknown illumination environments and does not require additional shape information from other sources.