arXiv research

Matrices satisfying the Restricted Isometry Property (RIP) play an important role in the areas of compressed sensing and statistical learning. RIP matrices with optimal parameters are mainly obtained via probabilistic arguments, as explicit constructions seem hard. It is therefore interesting to ask whether a fixed mat…

Differential structure on partial isometries over Grassmannian constructed.

In this paper we develop a complete theory of factorization for isometries of hyperbolic 4-space. Of special interest is the case where a pair of isometries is linked, that is, when a pair of isometries can be expressed each as compositions of two involutions, one of which is common to both isometries. Here we develop …

The paper analyzes conditions for solving low-rank matrix recovery problems with noisy measurements.

Oracle inequalities and variable selection properties for the Lasso in linear models have been established under a variety of different assumptions on the design matrix. We show in this paper how the different conditions and concepts relate to each other. The restricted eigenvalue condition (Bickel et al., 2009) or the…

In previous work, theoretical analysis based on the tensor Restricted Isometry Property (t-RIP) established the robust recovery guarantees of a low-tubal-rank tensor. The obtained sufficient conditions depend strongly on the assumption that the linear measurement maps satisfy the t-RIP. In this paper, by exploiting the…

It is natural to ask: what kinds of matrices satisfy the Restricted Eigenvalue (RE) condition? In this paper, we associate the RE condition (Bickel-Ritov-Tsybakov 09) with the complexity of a subset of the sphere in $\R^p$, where $p$ is the dimensionality of the data, and show that a class of random matrices with indep…

We analyze the condition number of random feature matrices and prove their well-conditioned nature.

We prove that a maximal totally complex submanifold $N^{2n}$ of the quaternionic projective space $\mathbb{H}\mathbb{P}^n$ ($n\geq 2$) is a parallel submanifold, provided one of the following conditions is satisfied: (1) $N$ is the orbit of a compact Lie group of isometries, (2) the restricted normal holonomy is a prop…

Sign-RIP improves robust low-rank matrix recovery by preserving norms even with corrupted measurements.

New analysis proves sketching operators' RIP guarantees for mixture models without importance sampling.

The fused lasso is analyzed for high-dimensional piecewise-constant regression coefficients.

We address some theoretical guarantees for Schatten-$p$ quasi-norm minimization ($p \in (0,1]$) in recovering low-rank matrices from compressed linear measurements. Firstly, using null space properties of the measurement operator, we provide a sufficient condition for exact recovery of low-rank matrices. This condition…

It is of interest to characterize algebraically the dynamical types of isometries of the complex and quaternionic hyperbolic planes. In the complex case, such a characterization is known from the work of Giraud-Goldman. In this paper, we offer an algebraic characterization of the isometries of the two-dimensional quate…

The restricted isometry property (RIP) is an integral tool in the analysis of various inverse problems with sparsity models. Motivated by the applications of compressed sensing and dimensionality reduction of low-rank tensors, we propose generalized notions of sparsity and provide a unified framework for the correspond…

We consider an inverse problem for a hyperbolic partial differential equation on a compact Riemannian manifold. Assuming that $Γ_1$ and $Γ_2$ are two disjoint open subsets of the boundary of the manifold we define the restricted Dirichlet-to-Neumann operator $Λ_{Γ_1,Γ_2}$. This operator corresponds the boundary measure…

We prove a Lipschitz-Volume rigidity theorem in Alexandrov geometry, that is, if a 1-Lipschitz map $f\colon X=\amalg X_\ell\to Y$ between Alexandrov spaces preserves volume, then it is a path isometry and an isometry when restricted to the interior of $X$. We furthermore characterize the metric structure on $Y$ with re…

New rigidity results for quasi-Einstein metrics with non-zero divergence-free vector fields.

Maps preserve distances in non-positively curved spaces.

A manifold is locally \emph{$k$-fold symmetric}, if for any point and any $k$-dimensional vector subspace tangent to this point there exists a local isometry such that this point is a fixed point and the differential of the isometry restricted to that $k$-dimensional vector subspace is minus the identity. We show that …

Paper introduces ENZ to measure significant coefficients in sparse recovery, improving over classical methods.

The paper explores conditions for constructing and extending infinitesimal isometries on special sub-Riemannian manifolds.

The restricted isometry property (RIP) is a universal tool for data recovery. We explore the implication of the RIP in the framework of generalized sparsity and group measurements introduced in the Part I paper. It turns out that for a given measurement instrument the number of measurements for RIP can be improved by o…

The study defines conditions for Finsler spacetime structures in $(α,β)$-metrics and identifies their isometries.

In this paper, we discuss the statistical properties of the $\ell_q$ optimization methods $(0<q\leq 1)$, including the $\ell_q$ minimization method and the $\ell_q$ regularization method, for estimating a sparse parameter from noisy observations in high-dimensional linear regression with either a deterministic or rando…

A Jacobi field on a Riemannian manifold M is defined along a geodesic. We generalize this notion to an arbitrary smooth curve, and call it an infinitesimal isometry along the curve. We give two approaches to this: 1) compute the complete prolongation of the Killing equation and then restrict to the curve, and 2) comput…

Let (P1) be certain elliptic free-boundary problem on a Riemannian manifold (M,g). In this paper we study the restrictions on the topology and geometry of the fibres (the level sets) of the solutions f to (P1). We give a technique based on certain remarkable property of the fibres (the analytic representation property)…

A number of recent work studied the effectiveness of feature selection using Lasso. It is known that under the restricted isometry properties (RIP), Lasso does not generally lead to the exact recovery of the set of nonzero coefficients, due to the looseness of convex relaxation. This paper considers the feature selecti…

Conditions for polynomial to be isometry of lattice, answering Hasse principles.

Nonconvex matrix recovery is known to contain no spurious local minima under a restricted isometry property (RIP) with a sufficiently small RIP constant $δ$. If $δ$ is too large, however, then counterexamples containing spurious local minima are known to exist. In this paper, we introduce a proof technique that is capa…

ARHT algorithm improves sparsity guarantees in convex optimization.

Deep 3D models are vulnerable to isometry transformations under adversarial attacks.

The multilabel learning problem with large number of labels, features, and data-points has generated a tremendous interest recently. A recurring theme of these problems is that only a few labels are active in any given datapoint as compared to the total number of labels. However, only a small number of existing work ta…

For a prime number $q\neq 2$ and $r>0$ we study, whether there exists an isometry of order $q^r$ acting on a free $\mathbb{Z}_{p^k}$-module equipped with a scalar product. We investigate, whether there exists such an isometry with no non-zero fixed points. Both questions are completely answered in this paper if $p\neq …

In a recent paper, it is shown that the LASSO algorithm exhibits "near-ideal behavior," in the following sense: Suppose $y = Az + η$ where $A$ satisfies the restricted isometry property (RIP) with a sufficiently small constant, and $\Vert η\Vert_2 \leq ε$. Then minimizing $\Vert z \Vert_1$ subject to $\Vert y - Az \Ver…

We show that if a shrinking soliton is asymptotic to a cone along an end then the isometry group of the cross-section of the cone embeds in the isometry group of the end of the shrinker. We also provide sufficient conditions for the isometries of the end to extend to the entire shrinker.

Being E a vector space with inner product and S the sphere of E, will be given a demonstration that every application of the sphere S itself it such that preserve inner product is the restriction of a linear isometry in E.

In this paper we study a Riemanian metric on the tangent bundle $T(M)$ of a Riemannian manifold $M$ which generalizes Sasaki metric and Cheeger Gromoll metric and a compatible almost complex structure which together with the metric confers to $T(M)$ a structure of locally conformal almost Kählerian manifold. This is th…

The paper extends localisation technique to multiple constraints in Euclidean spaces.

In this paper we study the performance of the Projected Gradient Descent(PGD) algorithm for $\ell_{p}$-constrained least squares problems that arise in the framework of Compressed Sensing. Relying on the Restricted Isometry Property, we provide convergence guarantees for this algorithm for the entire range of $0\leq p\…

This work builds on the foundation laid by Gordon and Wilson in the study of isometry groups of solvmanifolds, i.e. Riemannian manifolds admitting a transitive solvable group of isometries. We restrict ourselves to a natural class of solvable Lie groups called almost completely solvable; this class includes the complet…

This paper investigates the average-case time complexity of certifying RIP matrices.

The paper analyzes null infinity's geometry without restrictions.

New property ensures neural networks generalize well with limited data.

In this paper, we obtain the following generalisation of isometric $C^1$-immersion theorem of Nash and Kuiper. Let $M$ be a smooth manifold of dimension $m$ and $H$ a rank $k$ subbundle of the tangent bundle $TM$ with a Riemannian metric $g_H$. Then the pair $(H,g_H)$ defines a sub-Riemannian structure on $M$. We call …

Maps between certain Lipschitz manifolds are isometries if they preserve volume.

The requirement that a (non-Einstein) Kähler metric in any given complex dimension $m>2$ be almost-everywhere conformally Einstein turns out to be much more restrictive, even locally, than in the case of complex surfaces. The local biholomorphic-isometry types of such metrics depend, for each $m>2$, on three real param…

Study of isometries in spacetimes without observer horizons.