Search

This paper introduces a novel, non-deterministic method for embedding data in low-dimensional Euclidean space based on computing realizations of a Gaussian process depending on the geometry of the data. This type of embedding first appeared in (Adler et al, 2018) as a theoretical model for a generic manifold in high dimensions. In particular, we take the covariance function of the Gaussian process to be the heat kernel, and computing the embedding amounts to sketching a matrix representing the heat kernel. The Karhunen-Lo\`eve expansion reveals that the straight-line distances in the embedding approximate the diffusion distance in a probabilistic sense, avoiding the need for sharp cutoffs and maintaining some of the smaller-scale structure. Our method demonstrates further advantage in its robustness to outliers. We justify the approach with both theory and experiments., Comment: 28 pages

The purpose of this paper is to address a manifold-based version of Whitney's extension problem: Given a compact set $E\subset\mathbb{R}^n$, how can we tell if there exists a $d$-dimensional, $C^m$-smooth manifold $\mathcal{M}\supset E$? We provide an answer for compact manifolds with boundary in terms of a Glaeser refinement much like that used in the solution of the classical Whitney extension problem and a topological condition. This condition is the existence of a continuous selection for Grassmannian-valued functions, meant to reflect the collection of possible tangent spaces. We demonstrate the necessity of this condition in general and its non-redundancy in an example, while also showing it need not be checked when $d=1$., Comment: 37 pages, updated with a new example and some minor edits

The success of algorithms in the analysis of high-dimensional data is often attributed to the manifold hypothesis, which supposes that this data lie on or near a manifold of much lower dimension. It is often useful to determine or estimate the dimension of this manifold before performing dimension reduction, for instance. Existing methods for dimension estimation are calibrated using a flat unit ball. In this paper, we develop CA-PCA, a version of local PCA based instead on a calibration of a quadratic embedding, acknowledging the curvature of the underlying manifold. Numerous careful experiments show that this adaptation improves the estimator in a wide range of settings., Comment: 26 pages

Recent work of C. Fefferman and the first author has demonstrated that the linear system of equations \begin{equation*} \sum_{j=1}^M A_{ij}(x)F_j(x)=f_i(x)\hspace{.2in} (i=1,...,N), \end{equation*} has a $C^m$ solution $F=(F_1,...,F_M)$ if and only if $f_1,...,f_N$ satisfy a certain finite collection of partial differential equations. Here, the $A_{ij}$ are fixed semialgebraic functions. In this paper, we consider the analogous problem for systems of linear inequalities: \begin{equation*} \sum_{j=1}^M A_{ij}(x)F_j(x)\le f_i(x)\hspace{.2in} (i=1,...,N). \end{equation*} Our main result is a negative one, demonstrated by counterexample: the existence of a $C^m$ solution $F$ may not, in general, be determined via an analogous finite set of partial differential inequalities in $f_1,...,f_N$., Comment: 14 pages, updated version fixes a few typos