arXiv research

An elementary proof found for the double bubble problem in a specific norm.

Improved greedy 2-coordinate updates for optimization problems with constraints.

Diagonal linear networks converge to lasso regularization path during training.

The problem of joint feature selection across a group of related tasks has applications in many areas including biomedical informatics and computer vision. We consider the l2,1-norm regularized regression model for joint feature selection from multiple tasks, which can be derived in the probabilistic framework by assum…

We study the column subset selection problem with respect to the entrywise $\ell_1$-norm loss. It is known that in the worst case, to obtain a good rank-$k$ approximation to a matrix, one needs an arbitrarily large $n^{Ω(1)}$ number of columns to obtain a $(1+ε)$-approximation to the best entrywise $\ell_1$-norm low ra…

This paper considers the problem of recovering signals from compressed measurements contaminated with sparse outliers, which has arisen in many applications. In this paper, we propose a generative model neural network approach for reconstructing the ground truth signals under sparse outliers. We propose an iterative al…

In compressed sensing, in order to recover a sparse or nearly sparse vector from possibly noisy measurements, the most popular approach is $\ell_1$-norm minimization. Upper bounds for the $\ell_2$- norm of the error between the true and estimated vectors are given in [1] and reviewed in [2], while bounds for the $\ell_…

Tensor completion and robust principal component analysis have been widely used in machine learning while the key problem relies on the minimization of a tensor rank that is very challenging. A common way to tackle this difficulty is to approximate the tensor rank with the $\ell_1-$norm of singular values based on its …

A new PCA method using T$\ell_1$-norm outperforms existing methods.

Paper tackles outlier detection in signals modeled by generative models with theoretical guarantees.

The L 1-Sobolev inequality states that the L n/(n--1)-norm of a compactly supported function on Euclidean n-space is controlled by the L 1-norm of its gradient. The generalization to differential forms (due to Lanzani & Stein and Bourgain & Brezis) is recent, and states that a the L n/(n--1)-norm of a compactly support…

In this paper, we present GASG21 (Grassmannian Adaptive Stochastic Gradient for $L_{2,1}$ norm minimization), an adaptive stochastic gradient algorithm to robustly recover the low-rank subspace from a large matrix. In the presence of column outliers, we reformulate the batch mode matrix $L_{2,1}$ norm minimization with…

Paper shows no spurious local minima in a specific matrix factorization problem.

DNNs can learn complex functions efficiently by breaking the curse of dimensionality.

We consider the empirical risk minimization problem for linear supervised learning, with regularization by structured sparsity-inducing norms. These are defined as sums of Euclidean norms on certain subsets of variables, extending the usual $\ell_1$-norm and the group $\ell_1$-norm by allowing the subsets to overlap. T…

Derives integral formula for ReLU networks with limited weights.

Generalizes inequality for complete manifolds involving homology classes.

Improved LDA with capped l_{2,1}-norm reduces outlier sensitivity.

The ability to detect sparse signals from noisy high-dimensional data is a top priority in modern science and engineering. A sparse solution of the linear system $A ρ= b_0$ can be found efficiently with an $l_1$-norm minimization approach if the data is noiseless. Detection of the signal's support from data corrupted b…

The paper analyzes convergence properties of NGA and PAMe for $L_1$-norm PCA.

Enhances KLR for indefinite kernels with $L_1$-norm regularization.

Improved defect detection in layered materials using signal separation methods.

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…

Support vector machines (SVMs) are an important tool in modern data analysis. Traditionally, support vector machines have been fitted via quadratic programming, either using purpose-built or off-the-shelf algorithms. We present an alternative approach to SVM fitting via the majorization--minimization (MM) paradigm. Alg…

The paper studies the minimum ℓ₁-norm interpolator's risk behavior in over-parameterized settings.

We extend the results of our recent preprint [arXiv: 1811.00515] into higher dimensions $n \geq 4$. For minimizing harmonic maps $u\in W^{1,2}(Ω,\mathbb{S}^2)$ from $n$-dimensional domains into the two dimensional sphere we prove: (1) An extension of Almgren and Lieb's linear law, namely \[\mathcal{H}^{n-3}(\textrm{sin…

Develops efficient method for nonconvex problems using Regula Falsi.

We introduce a family of adaptive estimators on graphs, based on penalizing the $\ell_1$ norm of discrete graph differences. This generalizes the idea of trend filtering [Kim et al. (2009), Tibshirani (2014)], used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filteri…

Classical integral geometry takes place in Euclidean space, but one can attempt to imitate it in any other metric space. In particular, one can attempt this in R^n equipped with the metric derived from the p-norm. This has, in effect, been investigated intensively for 1<p<\infty, but not for p=1. We show that integral …

The popularity of algorithms based on Extreme Learning Machine (ELM), which can be used to train Single Layer Feedforward Neural Networks (SLFN), has increased in the past years. They have been successfully applied to a wide range of classification and regression tasks. The most commonly used methods are the ones based…

Recently, $l_{2,1}$ matrix norm has been widely applied to many areas such as computer vision, pattern recognition, biological study and etc. As an extension of $l_1$ vector norm, the mixed $l_{2,1}$ matrix norm is often used to find jointly sparse solutions. Moreover, an efficient iterative algorithm has been designed…

In many applications, high-dimensional data points can be well represented by low-dimensional subspaces. To identify the subspaces, it is important to capture a global and local structure of the data which is achieved by imposing low-rank and sparseness constraints on the data representation matrix. In low-rank sparse …

The $\ell_1$-norm fails to produce sparse solutions in Laplacian constrained graphical models, leading to a complete graph.

Forward stagewise regression follows a very simple strategy for constructing a sequence of sparse regression estimates: it starts with all coefficients equal to zero, and iteratively updates the coefficient (by a small amount $ε$) of the variable that achieves the maximal absolute inner product with the current residua…

We propose $\ell_1$ norm regularized quadratic surface support vector machine models for binary classification in supervised learning. We establish their desired theoretical properties, including the existence and uniqueness of the optimal solution, reduction to the standard SVMs over (almost) linearly separable data s…

The one-bit quantization is implemented by one single comparator that operates at low power and a high rate. Hence one-bit compressive sensing (1bit-CS) becomes attractive in signal processing. When measurements are corrupted by noise during signal acquisition and transmission, 1bit-CS is usually modeled as minimizing …

We consider the problem of learning a non-negative linear classifier with a $1$-norm of at most $k$, and a fixed threshold, under the hinge-loss. This problem generalizes the problem of learning a $k$-monotone disjunction. We prove that we can learn efficiently in this setting, at a rate which is linear in both $k$ and…

The $\ell$-1 norm based optimization is widely used in signal processing, especially in recent compressed sensing theory. This paper studies the solution path of the $\ell$-1 norm penalized least-square problem, whose constrained form is known as Least Absolute Shrinkage and Selection Operator (LASSO). A solution path …

Study pinches curvature under Laplacian G_2 flow, proving Weyl tensor norm blows up.

Recent work on adversarial attack and defense suggests that PGD is a universal $l_\infty$ first-order attack, and PGD adversarial training can significantly improve network robustness against a wide range of first-order $l_\infty$-bounded attacks, represented as the state-of-the-art defense method. However, an obvious …

ERM and RERM minimize error even with malicious label corruptions.

We study the density estimation problem with observations generated by certain dynamical systems that admit a unique underlying invariant Lebesgue density. Observations drawn from dynamical systems are not independent and moreover, usual mixing concepts may not be appropriate for measuring the dependence among these ob…

ResNets minimize circuit size for fitting data in HTMC regime.

New variational model preserves image contrasts and features using Weingarten map minimization.

In this paper we define, for each aspherical orientable 3-manifold $M$ endowed with a \emph{torus splitting} $Ţ$, a 2-dimensional fundamental $l_1$-class $[M]^{Ţ}$ whose $l_1$-norm has similar properties as the Gromov simplicial volume of $M$ (additivity under torus splittings and isometry under finite covering maps). …

Study Gaussian approximation for deep neural networks with random weights.

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. While naturally cast as a combinatorial optimization problem, variable or feature selection admits a convex relaxation through the regularization by the $\ell_1$-norm. In this paper, we consider situations where we…

Paper develops algorithms for sparse linear regression with generalized elastic net penalty.