arXiv research

Paper develops efficient AltMin algorithm for SRPCP robust matrix recovery.

Sharp condition found for Burer-Monteiro method to work for MaxCut-type SDPs.

The Burer-Monteiro method is one of the most widely used techniques for solving large-scale semidefinite programs (SDP). The basic idea is to solve a nonconvex program in $Y$, where $Y$ is an $n \times p$ matrix such that $X = Y Y^T$. In this paper, we show that this method can solve SDPs in polynomial time in a smooth…

This paper studies clustering for possibly high dimensional data (e.g. images, time series, gene expression data, and many other settings), and rephrase it as low rank matrix estimation in the PAC-Bayesian framework. Our approach leverages the well known Burer-Monteiro factorisation strategy from large scale optimisati…

Improved guarantees for nonconvex matrix factorization with rank overparameterization.

We study the projected gradient descent method on low-rank matrix problems with a strongly convex objective. We use the Burer-Monteiro factorization approach to implicitly enforce low-rankness; such factorization introduces non-convexity in the objective. We focus on constraint sets that include both positive semi-defi…

A new algorithm solves semidefinite programs using Langevin diffusion.

We address the rectangular matrix completion problem by lifting the unknown matrix to a positive semidefinite matrix in higher dimension, and optimizing a nonconvex objective over the semidefinite factor using a simple gradient descent scheme. With $O( μr^2 κ^2 n \max(μ, \log n))$ random observations of a $n_1 \times n…

We consider the non-square matrix sensing problem, under restricted isometry property (RIP) assumptions. We focus on the non-convex formulation, where any rank-$r$ matrix $X \in \mathbb{R}^{m \times n}$ is represented as $UV^\top$, where $U \in \mathbb{R}^{m \times r}$ and $V \in \mathbb{R}^{n \times r}$. In this paper…

Semidefinite programming (SDP) with diagonal constraints arise in many optimization problems, such as Max-Cut, community detection and group synchronization. Although SDPs can be solved to arbitrary precision in polynomial time, generic convex solvers do not scale well with the dimension of the problem. In order to add…

This work is concerned with the non-negative rank-1 robust principal component analysis (RPCA), where the goal is to recover the dominant non-negative principal components of a data matrix precisely, where a number of measurements could be grossly corrupted with sparse and arbitrary large noise. Most of the known techn…

Efficiently recovers low-tubal-rank tensors from few measurements.

Semidefinite programs (SDP) are important in learning and combinatorial optimization with numerous applications. In pursuit of low-rank solutions and low complexity algorithms, we consider the Burer--Monteiro factorization approach for solving SDPs. We show that all approximate local optima are global optima for the pe…

Low-rank factorization is a standard way to make structured optimization problems in machine learning more tractable by replacing matrix variables with compact factors. For positive semidefinite (PSD) variables, the symmetric Burer--Monteiro factorization (sBMF) writes $Z=XX^\top$ with a single low-rank factor $X$. A r…

New algorithm improves clustering accuracy without sacrificing scalability.

Gradient descent with preconditioning finds global optima in overparameterized nonconvex factorization.

This paper studies noisy low-rank matrix completion: given partial and noisy entries of a large low-rank matrix, the goal is to estimate the underlying matrix faithfully and efficiently. Arguably one of the most popular paradigms to tackle this problem is convex relaxation, which achieves remarkable efficacy in practic…

Geometric technique determines exactness of SDP robustness certificate.

Maximum A posteriori Probability (MAP) inference in graphical models amounts to solving a graph-structured combinatorial optimization problem. Popular inference algorithms such as belief propagation (BP) and generalized belief propagation (GBP) are intimately related to linear programming (LP) relaxation within the She…

Paper develops methods for non-quadratic loss low-rank matrix recovery.

Researchers describe and compare decompositions of Poincaré duality pairs.

The paper proposes and discusses semiorthogonal decompositions for moduli spaces of vector bundles.

The paper classifies decompositions of 3-sphere and lens spaces with handlebodies.

We combine aspects of the notions of finite decomposition complexity and asymptotic property C into a notion that we call finite APC-decomposition complexity. Any space with finite decomposition complexity has finite APC-decomposition complexity and any space with asymptotic property C has finite APC-decomposition comp…

This paper generalizes octahedral decomposition to links in thickened surfaces.

APGD algorithm reconstructs point set from partial distance measurements.

Researchers compute Goeritz groups for all (1,1)-link decompositions.

Study concordance of decompositions from defining sequences in 3-sphere.

Paper tackles robust matrix completion with heavy-tailed noise.

Given a Delaunay decomposition of a compact hyperbolic surface, one may record the topological data of the decomposition, together with the intersection angles between the `empty disks' circumscribing the regions of the decomposition. The main result of this paper is a characterization of when a given topological decom…

Study shows OAT decomposition generates unexplained profit and loss, while SU decompositions depend on risk factor order.

A new algorithm speeds up CP decomposition for large tensors.

Paper characterizes optimization landscape of Tucker decomposition.

A double pants decomposition of a 2-dimensional surface is a collection of two pants decomposition of this surface introduced in arXiv:1005.0073v2. There are two natural operations acting on double pants decompositions: flips and handle twists. It is shown in arXiv:1005.0073v2 that the groupoid generated by flips and h…

Smooth 4-manifolds have simple horizontal decompositions.

Let $\mathcal{J}^1$ be the real form of a complex simple Jordan algebra such that the automorphism group is $\mathrm{F}_{4(-20)}$. By using some orbit types of $\mathrm{F}_{4(-20)}$ on $\mathcal{J}^1$, for $\mathrm{F}_{4(-20)}$, explicitly, we give the Iwasawa decomposition, the Oshima--Sekiguchi's $K_ε-$Iwasawa decomp…

We study the topological types of pants decompositions of a surface by associating to any pants decomposition $P,$ in a natural way its pants decomposition graph, $Γ(P).$ This perspective provides a convenient way to analyze the maximum distance in the pants complex of any pants decomposition to a pants decomposition c…

New method uses random decompositions for high-dimensional Bayesian optimization.

New varifold example shows decomposition failure.

Derive new Euler-Ramanujan-type identities and infinite decompositions for zero mean curvature graphs in various spaces.

Decompositions on manifolds appear in various geometric structures. Necessary and sufficient conditions for quotient spaces of decompositions to be manifolds are widely characterized. We characterize necessary and sufficient conditions to be $k$-manifolds $(k = 1, 2)$, which generalize characterizations in the codimens…

Short proof for ideal polygons with near optimal orthogeodesic decomposition.

Paper introduces a new principle for fair redistribution of insurance surplus.

Simplifies solving noisy SDPs for low rank matrix recovery problems.

The paper defines and proves the existence of decompositions of integral varifolds.

We give an example of two JSJ decompositions of a group that are not related by conjugation, conjugation of edge-inclusions, and slide moves. This answers the question of Rips and Sela stated in "Cyclic splittings of finitely presented groups and the canonical JSJ decomposition," Ann. of Math. 146 (1997), 53-109. On th…

We consider a union of two pants decompositions of the same orientable 2-dimensional surface of any genus g. Each pants decomposition corresponds to some handlebody bounded by this surface, so two pants decompositions correspond to a Heegaard splitting of a 3-manifold. We introduce a groupoid FT acting on double pants …

We present a novel nonnegative tensor decomposition method, called Legendre decomposition, which factorizes an input tensor into a multiplicative combination of parameters. Thanks to the well-developed theory of information geometry, the reconstructed tensor is unique and always minimizes the KL divergence from an inpu…