arXiv research

In compressed sensing problems, $\ell_1$ minimization or Basis Pursuit was known to have the best provable phase transition performance of recoverable sparsity among polynomial-time algorithms. It is of great theoretical and practical interest to find alternative polynomial-time algorithms which perform better than $\e…

The paper classifies minimal immersions of flat 3- and 4-tori in spheres by their first eigenfunctions.

In this paper we develop a novel computational sensing framework for sensing and recovering structured signals. When trained on a set of representative signals, our framework learns to take undersampled measurements and recover signals from them using a deep convolutional neural network. In other words, it learns a tra…

We study the robustness properties of $\ell_1$ norm minimization for the classical linear regression problem with a given design matrix and contamination restricted to the dependent variable. We perform a fine error analysis of the $\ell_1$ estimator for measurements errors consisting of outliers coupled with noise. We…

We study the problem of globally recovering a dictionary from a set of signals via $\ell_1$-minimization. We assume that the signals are generated as i.i.d. random linear combinations of the $K$ atoms from a complete reference dictionary $D^*\in \mathbb R^{K\times K}$, where the linear combination coefficients are from…

We give a way of constructing real variations of mixed Hodge structures over compact Kähler manifolds by using mixed Hodge structures on Sullivan's $1$-minimal models of certain differential graded algebras associated with real variations of Hodge structures.

We refine the Morgan's work on mixed Hodge structures on Sullivan's $1$--minimal models by using non-abelian Hodge theory. As an application, we give explicit representatives of real unipotent variations of mixed Hodge structures over compact K"ahler manifolds.

New spectral clustering method using LASSO regularization for robust graph partitioning.

Recent results in Compressive Sensing have shown that, under certain conditions, the solution to an underdetermined system of linear equations with sparsity-based regularization can be accurately recovered by solving convex relaxations of the original problem. In this work, we present a novel primal-dual analysis on a …

Classical signal recovery based on $\ell_1$ minimization solves the least squares problem with all available measurements via sparsity-promoting regularization. In practice, it is often the case that not all measurements are available or required for recovery. Measurements might be corrupted/missing or they arrive sequ…

Given a smooth manifold $M$ equipped with a properly and discontinuous smooth action of a discrete group $G$, the nerve $M_{\bullet}G$ is a simplicial manifold and its vector space of differential forms $\operatorname{Tot}_{N}\left(A_{DR}(M_{\bullet}G)\right)$ carry a $C_{\infty}$-algebra structure $m_{\bullet}$. We sh…

Let $M^{n+1}$ be an orientable compact Riemannian manifold with positive Ricci curvature. We prove that the Almgren-Pitts width of $M^{n+1}$ is achieved by an orientable index $1$ minimal hypersurface with multiplicity $1$ and optimal regularity. This extends to dimensions $n+1\geq 8$ the results of Ketover-Marques-Nev…

We study the theoretical properties of learning a dictionary from $N$ signals $\mathbf x_i\in \mathbb R^K$ for $i=1,...,N$ via $l_1$-minimization. We assume that $\mathbf x_i$'s are $i.i.d.$ random linear combinations of the $K$ columns from a complete (i.e., square and invertible) reference dictionary $\mathbf D_0 \in…

This paper develops a novel deep recurrent neural network for sequential signal reconstruction.

High-dimensional data often lie in low-dimensional subspaces corresponding to different classes they belong to. Finding sparse representations of data points in a dictionary built using the collection of data helps to uncover low-dimensional subspaces and address problems such as clustering, classification, subset sele…

In this note we show the following result using the integral-geometric formula of R. Howard: Consider the totally geodesic $\mathbb{R}P^{2m}$ in $\mathbb{C}P^n$. Then it minimizes volume among the isotropic submanifolds in the same $\mathbb{Z}/2$ homology class in $\mathbb{C}P^n$ (but not among all submanifolds in this…

This paper concerns dictionary learning, i.e., sparse coding, a fundamental representation learning problem. We show that a subgradient descent algorithm, with random initialization, can provably recover orthogonal dictionaries on a natural nonsmooth, nonconvex $\ell_1$ minimization formulation of the problem, under mi…

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as $\ell_1$ minimization and nuclear norm minimization are…

The mean curvature flow is the gradient flow of volume functionals on the space of submanifolds. We prove a fundamental regularity result of the mean curvature flow in this paper: a Lipschitz submanifold with small local Lipschitz norm becomes smooth instantly along the mean curvature flow. This generalizes the regular…

The paper finds representations of surface groups in SO(4,1) with specific curvature properties.

We propose a framework that learns the graph structure underlying a set of smooth signals. Given $X\in\mathbb{R}^{m\times n}$ whose rows reside on the vertices of an unknown graph, we learn the edge weights $w\in\mathbb{R}_+^{m(m-1)/2}$ under the smoothness assumption that $\text{tr}{X^\top LX}$ is small. We show that …

New method improves smoothness of minimizing currents near singular points.

We discuss a general notion of "sparsity structure" and associated recoveries of a sparse signal from its linear image of reduced dimension possibly corrupted with noise. Our approach allows for unified treatment of (a) the "usual sparsity" and "usual $\ell_1$ recovery," (b) block-sparsity with possibly overlapping blo…

We propose to optimize the activation functions of a deep neural network by adding a corresponding functional regularization to the cost function. We justify the use of a second-order total-variation criterion. This allows us to derive a general representer theorem for deep neural networks that makes a direct connectio…

The main contribution of the paper is a new approach to subspace clustering that is significantly more computationally efficient and scalable than existing state-of-the-art methods. The central idea is to modify the regression technique in sparse subspace clustering (SSC) by replacing the $\ell_1$ minimization with a g…

Autonomy and adaptation of machines requires that they be able to measure their own errors. We consider the advantages and limitations of such an approach when a machine has to measure the error in a regression task. How can a machine measure the error of regression sub-components when it does not have the ground truth…

We consider the estimation of large covariance and precision matrices from high-dimensional sub-Gaussian or heavier-tailed observations with slowly decaying temporal dependence. The temporal dependence is allowed to be long-range so with longer memory than those considered in the current literature. We show that severa…

We propose and analyze an online algorithm for reconstructing a sequence of signals from a limited number of linear measurements. The signals are assumed sparse, with unknown support, and evolve over time according to a generic nonlinear dynamical model. Our algorithm, based on recent theoretical results for $\ell_1$-$…

The paper introduces a dynamic MVP model using high-frequency financial data.

New method estimates robust mean in high dimensions with minimized outliers.

We explore the graded and filtered formality properties of finitely generated groups by studying the various Lie algebras over a field of characteristic 0 attached to such groups, including the Malcev Lie algebra, the associated graded Lie algebra, the holonomy Lie algebra, and the Chen Lie algebra. We explain how thes…

In this paper, we investigate minimizing properties of the map $x/\|x\|$ from the Euclidean unit ball $\mathbf{B}^{n}$ to its boundary $\mathbb{S}^{n-1}$, for the weighted energy functionals $E^n\_{p,α}(u)=\int\_{\mathbf{B}^{n}} \|x\|^α\|\nabla u\|^p dx$. We establish the following induction principle: if the map $\fra…

Unified treatment of spacelike and timelike minimal surfaces via Liouville equation.

New deep-unfolded network improves video background separation.

Recently, the paradigm of unfolding iterative algorithms into finite-length feed-forward neural networks has achieved a great success in the area of sparse recovery. Benefit from available training data, the learned networks have achieved state-of-the-art performance in respect of both speed and accuracy. However, the …

We consider the problem of sparse coding, where each sample consists of a sparse linear combination of a set of dictionary atoms, and the task is to learn both the dictionary elements and the mixing coefficients. Alternating minimization is a popular heuristic for sparse coding, where the dictionary and the coefficient…

We present theoretical guarantees for an alternating minimization algorithm for the dictionary learning/sparse coding problem. The dictionary learning problem is to factorize vector samples $y^{1},y^{2},\ldots, y^{n}$ into an appropriate basis (dictionary) $A^*$ and sparse vectors $x^{1*},\ldots,x^{n*}$. Our algorithm …

Proposes GCCA for detecting latent relations in multiview data with sparse structures.

The paper derives inequalities for contact CR-warped product submanifolds in cosymplectic space forms.

We consider factoring low-rank tensors in the presence of outlying slabs. This problem is important in practice, because data collected in many real-world applications, such as speech, fluorescence, and some social network data, fit this paradigm. Prior work tackles this problem by iteratively selecting a fixed number …

We introduce a general framework to handle structured models (sparse and block-sparse with possibly overlapping blocks). We discuss new methods for their recovery from incomplete observation, corrupted with deterministic and stochastic noise, using block-$\ell_1$ regularization. While the current theory provides promis…

Study improves distributed linear estimation under adversarial conditions.

The paper studies Pansu spheres in a sub-Riemannian 3-sphere and their area-minimizing properties.

This paper considers the fundamental problem of learning a complete (orthogonal) dictionary from samples of sparsely generated signals. Most existing methods solve the dictionary (and sparse representations) based on heuristic algorithms, usually without theoretical guarantees for either optimality or complexity. The r…

We consider an online version of the robust Principle Component Analysis (PCA), which arises naturally in time-varying source separations such as video foreground-background separation. This paper proposes a compressive online robust PCA with prior information for recursively separating a sequences of frames into spars…

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse v…

Sharp results link DLN gradient flow to basis pursuit optimization and GHA phase transitions.

This paper focuses on convex constrained optimization problems, where the solution is subject to a convex inequality constraint. In particular, we aim at challenging problems for which both projection into the constrained domain and a linear optimization under the inequality constraint are time-consuming, which render …