More Like this

1. K-Deep Simplex: Manifold Learning via Local Dictionaries

   https://doi.org/10.1109/TSP.2023.3322820  

   Tasissa, Abiy; Tankala, Pranay; Murphy, James M.; Ba, Demba (January 2023, IEEE Transactions on Signal Processing)

   Duarte, Marco (Ed.)

   We propose K-Deep Simplex (KDS) which, given a set of data points, learns a dictionary comprising synthetic landmarks, along with representation coefficients supported on a simplex. KDS employs a local weighted l1 penalty that encourages each data point to represent itself as a convex combination of nearby landmarks. We solve the proposed optimization program using alternating minimization and design an efficient, interpretable autoencoder using algorithm unrolling. We theoretically analyze the proposed program by relating the weighted l1 penalty in KDS to a weighted ℓ0 program. Assuming that the data are generated from a Delaunay triangulation, we prove the equivalence of the weighted l1 and weighted l0 programs. We further show the stability of the representation coefficients under mild geometrical assumptions. If the representation coefficients are fixed, we prove that the sub-problem of minimizing over the dictionary yields a unique solution. Further, we show that low-dimensional representations can be efficiently obtained from the covariance of the coefficient matrix. Experiments show that the algorithm is highly efficient and performs competitively on synthetic and real data sets. 

   more » « less
2. A Dynamic Programming Framework for Generating Approximately Diverse and Optimal Solutions

   Gálvez, Waldo; Goswami, Mayank; Merino, Arturo; Park, GiBeom; Tsai, Meng-Tsung; Verdugo, Victor (January 2025, Arxiv)

   We develop a general framework, called approximately-diverse dynamic programming (ADDP) that can be used to generate a collection of k≥2 maximally diverse solutions to various geometric and combinatorial optimization problems. Given an approximation factor 0≤c≤1, this framework also allows for maximizing diversity in the larger space of c-approximate solutions. We focus on two geometric problems to showcase this technique: 1. Given a polygon P, an integer k≥2 and a value c≤1, generate k maximally diverse c-nice triangulations of P. Here, a c-nice triangulation is one that is c-approximately optimal with respect to a given quality measure σ. 2. Given a planar graph G, an integer k≥2 and a value c≤1, generate k maximally diverse c-optimal Independent Sets (or, Vertex Covers). Here, an independent set S is said to be c-optimal if |S|≥c|S′| for any independent set S′ of G. Given a set of k solutions to the above problems, the diversity measure we focus on is the average distance between the solutions, where d(X,Y)=|XΔY|. For arbitrary polygons and a wide range of quality measures, we give poly(n,k) time (1−Θ(1/k))-approximation algorithms for the diverse triangulation problem. For the diverse independent set and vertex cover problems on planar graphs, we give an algorithm that runs in time 2^(O(k.δ^(−1).ϵ^(−2)).n^O(1/ϵ) and returns (1−ϵ)-approximately diverse (1−δ)c-optimal independent sets or vertex covers. Our triangulation results are the first algorithmic results on computing collections of diverse geometric objects, and our planar graph results are the first PTAS for the diverse versions of any NP-complete problem. Additionally, we also provide applications of this technique to diverse variants of other geometric problems. 

   more » « less
3. A Fast Proximal Point Method for Computing Exact Wasserstein Distance

   Xie, Yujia; Wang, Xiangfeng; Wang, Ruijia; Zha, Hongyuan (January 2019, Uncertainty in artificial intelligence)

   Wasserstein distance plays increasingly important roles in machine learning, stochastic programming and image processing. Major efforts have been under way to address its high computational complexity, some leading to approximate or regularized variations such as Sinkhorn distance. However, as we will demonstrate, regularized variations with large regularization parameter will degradate the performance in several important machine learning applications, and small regularization parameter will fail due to numerical stability issues with existing algorithms. We address this challenge by developing an Inexact Proximal point method for exact Optimal Transport problem (IPOT) with the proximal operator approximately evaluated at each iteration using projections to the probability simplex. The algorithm (a) converges to exact Wasserstein distance with theoretical guarantee and robust regularization parameter selection, (b) alleviates numerical stability issue, (c) has similar computational complexity to Sinkhorn, and (d) avoids the shrinking problem when apply to generative models. Furthermore, a new algorithm is proposed based on IPOT to obtain sharper Wasserstein barycenter. 

   more » « less
4. Learning the Structure of Large Networked Systems Obeying Conservation Laws

   Rayas, A.; Anguluri, R.; Dasarathy, G. (January 2022, Advances in Neural Information Processing Systems 35 (NeurIPS 2022))

   Many networked systems such as electric networks, the brain, and social networks of opinion dynamics are known to obey conservation laws. Examples of this phenomenon include the Kirchoff laws in electric networks and opinion consensus in social networks. Conservation laws in networked systems are modeled as balance equations of the form X=B*Y, where the sparsity pattern of B*∈R^{p×p} captures the connectivity of the network on p nodes, and Y, X ∈ R^p are vectors of ''potentials'' and ''injected flows'' at the nodes respectively. The node potentials Y cause flows across edges which aim to balance out the potential difference, and the flows X injected at the nodes are extraneous to the network dynamics. In several practical systems, the network structure is often unknown and needs to be estimated from data to facilitate modeling, management, and control. To this end, one has access to samples of the node potentials Y, but only the statistics of the node injections X. Motivated by this important problem, we study the estimation of the sparsity structure of the matrix B* from n samples of Y under the assumption that the node injections X follow a Gaussian distribution with a known covariance Σ_X. We propose a new ℓ1-regularized maximum likelihood estimator for tackling this problem in the high-dimensional regime where the size of the network may be vastly larger than the number of samples n. We show that this optimization problem is convex in the objective and admits a unique solution. Under a new mutual incoherence condition, we establish sufficient conditions on the triple (n,p,d) for which exact sparsity recovery of B* is possible with high probability; d is the degree of the underlying graph. We also establish guarantees for the recovery of B* in the element-wise maximum, Frobenius, and operator norms. Finally, we complement these theoretical results with experimental validation of the performance of the proposed estimator on synthetic and real-world data. 

   more » « less
5. Topological k-Metrics

   https://doi.org/10.4230/LIPIcs.SoCG.2024.13  

   Barkan, Willow; Bennett, Huck; Nayyeri, Amir (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang; Phillips, Jeff M (Ed.)

   Metric spaces (X, d) are ubiquitous objects in mathematics and computer science that allow for capturing pairwise distance relationships d(x, y) between points x, y ∈ X. Because of this, it is natural to ask what useful generalizations there are of metric spaces for capturing "k-wise distance relationships" d(x_1, …, x_k) among points x_1, …, x_k ∈ X for k > 2. To that end, Gähler (Math. Nachr., 1963) (and perhaps others even earlier) defined k-metric spaces, which generalize metric spaces, and most notably generalize the triangle inequality d(x₁, x₂) ≤ d(x₁, y) + d(y, x₂) to the "simplex inequality" d(x_1, …, x_k) ≤ ∑_{i=1}^k d(x_1, …, x_{i-1}, y, x_{i+1}, …, x_k). (The definition holds for any fixed k ≥ 2, and a 2-metric space is just a (standard) metric space.) In this work, we introduce strong k-metric spaces, k-metric spaces that satisfy a topological condition stronger than the simplex inequality, which makes them "behave nicely." We also introduce coboundary k-metrics, which generalize 𝓁_p metrics (and in fact all finite metric spaces induced by norms) and minimum bounding chain k-metrics, which generalize shortest path metrics (and capture all strong k-metrics). Using these definitions, we prove analogs of a number of fundamental results about embedding finite metric spaces including Fréchet embedding (isometric embedding into 𝓁_∞) and isometric embedding of all tree metrics into 𝓁₁. We also study relationships between families of (strong) k-metrics, and show that natural quantities, like simplex volume, are strong k-metrics. 

   more » « less