skip to main content


Search for: All records

Award ID contains: 1752202

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Abstract

    Archetypal analysis (AA) is an unsupervised learning method for exploratory data analysis. One major challenge that limits the applicability of AA in practice is the inherent computational complexity of the existing algorithms. In this paper, we provide a novel approximation approach to partially address this issue. Utilizing probabilistic ideas from high-dimensional geometry, we introduce two preprocessing techniques to reduce the dimension and representation cardinality of the data, respectively. We prove that provided data are approximately embedded in a low-dimensional linear subspace and the convex hull of the corresponding representations is well approximated by a polytope with a few vertices, our method can effectively reduce the scaling of AA. Moreover, the solution of the reduced problem is near-optimal in terms of prediction errors. Our approach can be combined with other acceleration techniques to further mitigate the intrinsic complexity of AA. We demonstrate the usefulness of our results by applying our method to summarize several moderately large-scale datasets.

     
    more » « less
  2. Free, publicly-accessible full text available April 1, 2024
  3. Free, publicly-accessible full text available March 31, 2024
  4. null (Ed.)
    Semi-supervised and unsupervised machine learning methods often rely on graphs to model data, prompting research on how theoretical properties of operators on graphs are leveraged in learning problems. While most of the existing literature focuses on undirected graphs, directed graphs are very important in practice, giving models for physical, biological or transportation networks, among many other applications. In this paper, we propose a new framework for rigorously studying continuum limits of learning algorithms on directed graphs. We use the new framework to study the PageRank algorithm and show how it can be interpreted as a numerical scheme on a directed graph involving a type of normalised graph Laplacian . We show that the corresponding continuum limit problem, which is taken as the number of webpages grows to infinity, is a second-order, possibly degenerate, elliptic equation that contains reaction, diffusion and advection terms. We prove that the numerical scheme is consistent and stable and compute explicit rates of convergence of the discrete solution to the solution of the continuum limit partial differential equation. We give applications to proving stability and asymptotic regularity of the PageRank vector. Finally, we illustrate our results with numerical experiments and explore an application to data depth. 
    more » « less
  5. null (Ed.)
    Recently Fraser and Schoen showed that the solution of a certain extremal Steklov eigenvalue problem on a compact surface with boundary can be used to generate a free boundary minimal surface, i.e. , a surface contained in the ball that has (i) zero mean curvature and (ii) meets the boundary of the ball orthogonally (doi: 10.1007/s00222-015-0604-x ). In this paper, we develop numerical methods that use this connection to realize free boundary minimal surfaces. Namely, on a compact surface, Σ, with genus γ and b boundary components, we maximize σ j (Σ, g )  L ( ∂ Σ, g ) over a class of smooth metrics, g , where σ j (Σ, g ) is the j th nonzero Steklov eigenvalue and L ( ∂ Σ, g ) is the length of ∂ Σ. Our numerical method involves (i) using conformal uniformization of multiply connected domains to avoid explicit parameterization for the class of metrics, (ii) accurately solving a boundary-weighted Steklov eigenvalue problem in multi-connected domains, and (iii) developing gradient-based optimization methods for this non-smooth eigenvalue optimization problem. For genus γ = 0 and b = 2, …, 9, 12, 15, 20 boundary components, we numerically solve the extremal Steklov problem for the first eigenvalue. The corresponding eigenfunctions generate a free boundary minimal surface, which we display in striking images. For higher eigenvalues, numerical evidence suggests that the maximizers are degenerate, but we compute local maximizers for the second and third eigenvalues with b = 2 boundary components and for the third and fifth eigenvalues with b = 3 boundary components. 
    more » « less
  6. null (Ed.)