Search

We consider the problem of recovering elements of a low-dimensional model from under-determined linear measurements. To perform recovery, we consider the minimization of a convex regularizer subject to a data fit constraint. Given a model, we ask ourselves what is the 'best' convex regularizer to perform its recovery. To answer this question, we define an optimal regularizer as a function that maximizes a compliance measure with respect to the model. We introduce and study several notions of compliance. We give analytical expressions for compliance measures based on the best-known recovery guarantees with the restricted isometry property. These expressions permit to show the optimality of the |$\ell ^{1}$| -norm for sparse recovery and of the nuclear norm for low-rank matrix recovery for these compliance measures. We also investigate the construction of an optimal convex regularizer using the examples of sparsity in levels and of sparse plus low-rank models. [ABSTRACT FROM AUTHOR]

We provide high-probability bounds on the condition number of random feature matrices. In particular, we show that if the complexity ratio |$N/m$|⁠ , where |$N$| is the number of neurons and |$m$| is the number of data samples, scales like |$\log ^{-1}(N)$| or |$\log (m)$|⁠ , then the random feature matrix is well-conditioned. This result holds without the need of regularization and relies on establishing various concentration bounds between dependent components of the random feature matrix. Additionally, we derive bounds on the restricted isometry constant of the random feature matrix. We also derive an upper bound for the risk associated with regression problems using a random feature matrix. This upper bound exhibits the double descent phenomenon and indicates that this is an effect of the double descent behaviour of the condition number. The risk bounds include the underparameterized setting using the least squares problem and the overparameterized setting where using either the minimum norm interpolation problem or a sparse regression problem. For the noiseless least squares or sparse regression cases, we show that the risk decreases as |$m$| and |$N$| increase. The risk bound matches the optimal scaling in the literature and the constants in our results are explicit and independent of the dimension of the data. [ABSTRACT FROM AUTHOR]

This paper aims to study the performance of the amplitude-based model |$\widehat{{\boldsymbol x}} \in \mathop{\mathrm{argmin}}\limits _{{\boldsymbol x}\in \mathbb{C}^{d}}\sum _{j=1}^{m}\left (|\langle{\boldsymbol a}_{j},{\boldsymbol x}\rangle |-b_{j}\right)^{2}$|⁠ , where |$b_{j}:=|\langle{\boldsymbol a}_{j},{\boldsymbol x}_{0}\rangle |+\eta _{j}$| and |${\boldsymbol x}_{0}\in \mathbb{C}^{d}$| is a target signal. The model is raised in phase retrieval as well as in absolute value rectification neural networks. Many efficient algorithms have been developed to solve it in the past decades. However, there are very few results available regarding the estimation performance in the complex case under noisy conditions. In this paper, we present a theoretical guarantee on the amplitude-based model for the noisy complex phase retrieval problem. Specifically, we show that |$\min _{\theta \in [0,2\pi)}\|\widehat{{\boldsymbol x}}-\exp (\mathrm{i}\theta)\cdot{\boldsymbol x}_{0}\|_{2} \lesssim \frac{\|{\boldsymbol \eta }\|_{2}}{\sqrt{m}}$| holds with high probability provided the measurement vectors |${\boldsymbol a}_{j}\in \mathbb{C}^{d},$|   |$j=1,\ldots ,m,$| are i.i.d. complex sub-Gaussian random vectors and |$m\gtrsim d$|⁠. Here |${\boldsymbol \eta }=(\eta _{1},\ldots ,\eta _{m})\in \mathbb{R}^{m}$| is the noise vector without any assumption on the distribution. Furthermore, we prove that the reconstruction error is sharp. For the case where the target signal |${\boldsymbol x}_{0}\in \mathbb{C}^{d}$| is sparse, we establish a similar result for the nonlinear constrained |$\ell _{1}$| minimization model. To accomplish this, we leverage a strong version of restricted isometry property for an operator on the space of simultaneous low-rank and sparse matrices. [ABSTRACT FROM AUTHOR]

The ratio of |$\ell _{1}$| and |$\ell _{2}$| norms, denoted as |$\ell _{1}/\ell _{2}$|⁠ , has presented prominent performance in promoting sparsity. By adding partial support information to the standard |$\ell _{1}/\ell _{2}$| minimization, in this paper, we introduce a novel model, i.e. the weighted |$\ell _{1}/\ell _{2}$| minimization, to recover sparse signals from the linear measurements. The restricted isometry property based conditions for sparse signal recovery in both noiseless and noisy cases through the weighted |$\ell _{1}/\ell _{2}$| minimization are established. And we show that the proposed conditions are weaker than the analogous conditions for standard |$\ell _{1}/\ell _{2}$| minimization when the accuracy of the partial support information is at least |$50\%$|⁠. Moreover, we develop effective algorithms and illustrate our results via extensive numerical experiments on synthetic data in both noiseless and noisy cases. [ABSTRACT FROM AUTHOR]

Compressive learning forms the exciting intersection between compressed sensing and statistical learning where one exploits sparsity of the learning model to reduce the memory and/or computational complexity of the algorithms used to solve the learning task. In this paper, we look at the independent component analysis (ICA) model through the compressive learning lens. In particular, we show that solutions to the cumulant-based ICA model have a particular structure that induces a low-dimensional model set that resides in the cumulant tensor space. By showing that a restricted isometry property holds for random cumulants e.g. Gaussian ensembles, we prove the existence of a compressive ICA scheme. Thereafter, we propose two algorithms of the form of an iterative projection gradient and an alternating steepest descent algorithm for compressive ICA, where the order of compression asserted from the restricted isometry property is realized through empirical results. We provide analysis of the CICA algorithms including the effects of finite samples. The effects of compression are characterized by a trade-off between the sketch size and the statistical efficiency of the ICA estimates. By considering synthetic and real datasets, we show the substantial memory gains achieved over well-known ICA algorithms by using one of the proposed CICA algorithms. [ABSTRACT FROM AUTHOR]

The absence of spurious local minima in certain nonconvex low-rank matrix recovery problems has been of recent interest in computer science, machine learning and compressed sensing since it explains the convergence of some low-rank optimization methods to global optima. One such example is low-rank matrix sensing under restricted isometry properties (RIPs). It can be formulated as a minimization problem for a quadratic function on the Riemannian manifold of low-rank matrices, with a positive semidefinite Riemannian Hessian that acts almost like an identity on low-rank matrices. In this work new estimates for singular values of local minima for such problems are given, which lead to improved bounds on RIP constants to ensure absence of nonoptimal local minima and sufficiently negative curvature at all other critical points. A geometric viewpoint is taken, which is inspired by the fact that the Euclidean distance function to a rank- |$k$| matrix possesses no critical points on the corresponding embedded submanifold of rank- |$k$| matrices except for the single global minimum. [ABSTRACT FROM AUTHOR]

Quantized compressive sensing deals with the problem of coding compressive measurements of low-complexity signals with quantized, finite precision representations, i.e. a mandatory process involved in any practical sensing model. While the resolution of this quantization impacts the quality of signal reconstruction, there exist incompatible combinations of quantization functions and sensing matrices that proscribe arbitrarily low reconstruction error when the number of measurements increases. This work shows that a large class of random matrix constructions known to respect the restricted isometry property (RIP) is 'compatible' with a simple scalar and uniform quantization if a uniform random vector, or a random dither , is added to the compressive signal measurements before quantization. In the context of estimating low-complexity signals (e.g. sparse or compressible signals, low-rank matrices) from their quantized observations, this compatibility is demonstrated by the existence of (at least) one signal reconstruction method, the projected back projection , whose reconstruction error decays when the number of measurements increases. Interestingly, given one RIP matrix and a single realization of the dither, a small reconstruction error can be proved to hold uniformly for all signals in the considered low-complexity set. We confirm these observations numerically in several scenarios involving sparse signals, low-rank matrices and compressible signals, with various RIP matrix constructions such as sub-Gaussian random matrices and random partial discrete cosine transform matrices. [ABSTRACT FROM AUTHOR]

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 corresponding RIP, in particular when combined with isotropic group actions. Our results extend an approach by Rudelson and Vershynin to a much broader context including commutative and non-commutative function spaces. Moreover, our Banach space notion of sparsity applies to affine group actions. The generalized approach in particular applies to high-order tensor products. [ABSTRACT FROM AUTHOR]

Let M be a compact connected pseudo-Riemannian manifold on which a solvable connected Lie group G of isometries acts transitively. We show that G acts almost freely on M and that the metric onM is induced by a bi-invariant pseudo-Riemannian metric on G. Furthermore, we show that the identity component of the isometry group ofM coincides with G. The proofs rely on a combination of density properties for uniform subgroups of solvable Lie groups and the reduction theory of pseudo-Riemannian metric Lie groups. [ABSTRACT FROM AUTHOR]

Recently, many works have focused on the characterization of non-linear dimensionality reduction methods obtained by quantizing linear embeddings, e.g., to reach fast processing time, efficient data compression procedures, novel geometry-preserving embeddings or to estimate the information/bits stored in this reduced data representation. In this work, we prove that many linear maps known to respect the restricted isometry property (RIP) can induce a quantized random embedding with controllable multiplicative and additive distortions with respect to the pairwise distances of the data points beings considered. In other words, linear matrices having fast matrix-vector multiplication algorithms (e.g., based on partial Fourier ensembles or on the adjacency matrix of unbalanced expanders) can be readily used in the definition of fast quantized embeddings with small distortions. This implication is made possible by applying right after the linear map an additive and random "dither" that stabilizes the impact of the uniform scalar quantization operator applied afterwards. For different categories of RIP matrices, i.e., for different linear embeddings of a metric space (K⊂Rn,ℓq) in (Rm,ℓp) with p,q≥1, we derive upper bounds on the additive distortion induced by quantization, showing that it decays either when the embedding dimension m increases or when the distance of a pair of embedded vectors in K decreases. Finally, we develop a novel "bi-dithered" quantization scheme, which allows for a reduced distortion that decreases when the embedding dimension grows and independently of the considered pair of vectors. [ABSTRACT FROM AUTHOR]

Weighted ℓ1-minimization has been studied as a technique for the reconstruction of a sparse signal from compressively sampled measurements when prior information about the signal, in the form of a support estimate, is available. In thiswork, we study the recovery conditions and the associated recovery guarantees of weighted ℓ1-minimization when arbitrarily many distinct weights are permitted. For example, such a setup might be used when one has multiple estimates for the support of a signal, and these estimates have varying degrees of accuracy. Our analysis yields an extension to existing works that assume only a single support estimate set upon which a constant weight is applied. We include numerical experiments, with both synthetic signals and real video data, that demonstrate the benefits of allowing non-uniform weights in the reconstruction procedure. [ABSTRACT FROM AUTHOR]