Search

In this paper, we study an unconstrained l2,p minimization and its associated iteratively reweighted least squares algorithm (UBIRLS) for recovering block sparse signals. Wang et al. [Y. Wang, J. Wang and Z. Xu, On recovery of block-sparse signals via mixed l2/lq (0 < q ≤ 1) norm minimization, EURASIP J. Adv. Signal Process. 2013(76) (2013) 76] have used numerical experiments to show the remarkable performance of UBIRLS algorithm for recovering a block sparse signal, but no theoretical analysis such as convergence and convergence rate analysis of UBIRLS algorithm was given. We focus on providing convergence and convergence rate analysis of UBIRLS algorithm for block sparse recovery problem. First, the convergence of UBIRLS is proved strictly. Second, based on the block restricted isometry property (block RIP) of linear measurement matrix A, we give the error bound analysis of the UBIRLS algorithm. Lastly, we also characterize the local convergence behavior of the UBIRLS algorithm. The simplicity of UBIRLS algorithm, along with the theoretical guarantees provided in this paper, will make a compelling case for its adoption as a standard tool for block sparse recovery. [ABSTRACT FROM AUTHOR]

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 introduces a nonconvex ℓ1−2-analysis model: minx(∥D∗x∥ 1 −∥D∗x∥ 2)s.t. Ax = y, where A is a measurement matrix and D is a tight frame. Our main motivation is to generalize the sparse recovery via ℓ1 − ℓ2 minimization to this new model. As a nonconvex model, it is well known that its global minimizer and local minimizer are usually inconsistent. This paper provides a type of null space property (NSP) characterization which are necessary and sufficient conditions for the measurement matrix A such that a vector x can be recovered from Ax with a tight frame D via ℓ1−2-analysis local minimization, or any vector x can be uniformly recovered from Ax with a tight frame D via ℓ1−2-analysis minimization locally and globally. [ABSTRACT FROM AUTHOR]

We propose the Rescaled Matching Pursuit (RMP) algorithm to recover sparse signals in high-dimensional Euclidean spaces. The RMP algorithm has less computational complexity than other greedy-type algorithms, such as Orthogonal Matching Pursuit (OMP). We show that if the restricted isometry property is satisfied, then the upper bound of the error between the original signal and its approximation can be derived. Furthermore, we prove that the RMP algorithm can find the correct support of sparse signals from random measurements with a high probability. Our numerical experiments also verify this conclusion and show that RMP is stable with the noise. So, the RMP algorithm is a suitable method for recovering sparse signals. [ABSTRACT FROM AUTHOR]

This paper concentrates on the recovery of block-sparse signals, which are not only sparse but also nonzero elements are arrayed into some blocks (clusters) rather than being arbitrary distributed all over the vector, from linear measurements. We establish high-order sufficient conditions based on block RIP, which could ensure the exact recovery of every block s-sparse signal in the noiseless case via mixed l 2 / l p {l_{2}/l_{p}} minimization method, and the stable and robust recovery in the case that signals are not accurately block-sparse in the presence of noise. Additionally, a lower bound on necessary number of random Gaussian measurements is gained for the condition to be true with overwhelming probability. Furthermore, a series of numerical experiments are conducted to demonstrate the performance of the mixed l 2 / l p {l_{2}/l_{p}} minimization. To the best of the authors’ knowledge, the recovery guarantees established in this paper are superior to those currently available. [ABSTRACT FROM AUTHOR]

The projected gradient method for matrix completion is generalized towards the higher-dimensional case of low-rank Tucker tensors. It is shown that an operation order rearrangement in the common projected gradient approach provides a complexity improvement. An even better algorithm complexity can be obtained by replacing the completion operator by a general operator that satisfies restricted isometry property; however, such a replacement transforms the completion algorithm into an approximation algorithm. [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]

This paper considers the L 1 -minimization problem for sparse signal and image reconstruction by using projection neural networks (PNNs). Firstly, a new finite-time converging projection neural network (FtPNN) is presented. Building upon FtPNN, a new fixed-time converging PNN (FxtPNN) is designed. Under the condition that the projection matrix satisfies the Restricted Isometry Property (RIP), the stability in the sense of Lyapunov and the finite-time convergence property of the proposed FtPNN are proved; then, it is proven that the proposed FxtPNN is stable and converges to the optimum solution regardless of the initial values in fixed time. Finally, simulation examples with signal and image reconstruction are carried out to show the effectiveness of our proposed two neural networks, namely FtPNN and FxtPNN. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the conditions for the exact or stable recovery of weighted k-sparse signals in weighted sparse phase retrieval in our previous work [11] from the weighted ℓ1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\ell _1$$\end{document} minimization to the weighted ℓq(0k-sparse signal from its noiseless phaseless measurements via the weighted ℓq(0k-sparse signal from its noisy phaseless measurements via the weighted ℓq(0

In practical engineering scenarios, constraints arising from sensor placement, quantity, and the limitations of current testing technologies often lead to turbulence data characterized by low resolution and irregular structures. Turbulence super-resolution reconstruction is crucial for extracting finer details from irregularly structured, low-resolution measurement data, thereby facilitating comprehensive flow field analyses. This article introduces a sparse learning model (Embedding Restricted Isometry Property Autoencoder (RIP-AE)) for achieving super-resolution reconstruction of flow fields by obtaining compressed representations and sparse transform domain information. In this model, we embed the Restricted Isometry Property (RIP) condition to ensure the effectiveness of compressed representations and sparse transform domains, thereby enhancing the super-resolution reconstruction accuracy of the model. To assess the performance of the RIP-AE model, we utilized data sets of flow around a cylinder at different Reynolds numbers generated by unsteady Reynolds-Averaged Navier–Stokes simulations. We sequentially validate the effectiveness of the RIP condition at different Reynolds numbers (ranging from 1,000 to 500,000) and compare the reconstruction results of the RIP-AE model with those of the downsampled skip-connection/multi-scale (DSC/MS) and MS-AE models under different sampling ratios. The results indicate that the RIP-AE model excels in terms of L2 relative error and demonstrates the capability to achieve high-precision flow field reconstruction even under high sampling ratios. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the low-rank matrix recovery problem from linear observations. Inspired by the matrix Lasso and Dantzig selector, we propose nuclear norm regularized models with two data fitting items: ℓ 2 -loss function and Dantzig selector. We establish the recovery errors for both constrained and unconstrained models under the matrix restricted isometry property frame. For the unconstrained model, we obtain a tighter error bound compared with the previous study by W. Wang et al. (2021) under certain conditions. Furthermore, we design an effective solving algorithm for the proposed unconstrained model. Our numerical experiments demonstrate that our method outperforms the Lasso and Dantzig selector models. • Stable recovery errors for nuclear norm regularized models are established. • Efficient algorithm based on PSS method for low-rank matrix recovery is proposed. • Our method achieves good recovery performance in numerical experiments. [ABSTRACT FROM AUTHOR]

In this paper, we study compressed data separation (CDS) problem, i.e., sparse data separation from a few linear random measurements. We propose the nonconvex ℓq-split analysis with ℓ∞-constraint and 0 < q ≤ 1. We call the algorithm ℓq-split-analysis Dantzig selector (ℓq-split-analysis DS). We show that the two distinct subcomponents that are approximately sparse in terms of two different dictionaries could be stably approximated via the ℓq-split-analysis DS, provided that the measurement matrix satisfies either a classical D-RIP (Restricted Isometry Property with respect to Dictionaries and ℓ2 norm) or a relatively new (D, q)-RIP (RIP with respect to Dictionaries and ℓq-quasi norm) condition and the two different dictionaries satisfy a mutual coherence condition between them. For the Gaussian random measurements, the measurement number needed for the (D, q)-RIP condition is far less than those needed for the D-RIP condition and the (D, 1)-RIP condition when q is small enough. [ABSTRACT FROM AUTHOR]

This article proposes a continuous-time neurodynamic approach for solving the rank minimization under affine constraints. As opposed to the traditional neurodynamic approach, the proposed neurodynamic approach extends the form of the variables from the vector form to the matrix form. First, a continuous-time neurodynamic approach with variables in matrix form is developed by combining the optimal rank r projection and the gradient. Then, the optimality of the proposed neurodynamic approach is rigorously analyzed by demonstrating that the objective function satisfies the functional property which is called as (2 r , 4 r) -restricted strong convexity and smoothness ((2 r , 4 r) -RSCS). Furthermore, the convergence and stability analysis of the proposed neurodynamic approach is rigorously conducted by establishing appropriate Lyapunov functions and considering the relevant restricted isometry property (RIP) condition associated with the affine transformation. Finally, through experiments involving low-rank matrix recovery under affine transformations and the completion of low-rank real image, the effectiveness of this approach has been demonstrated, along with its superiority compared to the vector-based approach. [ABSTRACT FROM AUTHOR]

In numerous applications, such as DNA microarrays, face recognition, and spectral unmixing, we need to acquire a non-negative K -sparse signal x from an underdetermined linear model y = A x + v , where A is a sensing matrix and v is a noise vector. In this paper, we first propose a ReLU-based hard-thresholding algorithm (RHT) to recover x by taking advantage of its non-negative sparsity. Two sufficient conditions for stable recovery with RHT are then developed, which are respectively based on the restricted isometry property (RIP) and mutual coherence of the sensing matrix A. As far as we know, these two sufficient conditions are the best for hard-thresholding-type algorithms. Numerical experiments show that RHT has better overall recovery performance in the recovery non-negative sparse signals than the non-negative least squares (NNLS) algorithm, some hard-thresholding-type algorithms including the iterative hard-thresholding (IHT) algorithm, hard-thresholding pursuit (HTP), Newton-step-based iterative hard-thresholding algorithm (NSIHT), and Newton-step-based hard-thresholding pursuit (NSHTP), several non-negative sparse recovery approaches including non-negative orthogonal matching pursuit (NNOMP), fast NNOMP (FNNOMP), non-negative orthogonal least squares (NNOLS), and non-negative regularization (NNREG) method. In terms of efficiency, RHT has a similar performance to IHT, and is much more efficient than other tested algorithms. • Efficient hard-thresholding-type algorithm for non-negative sparse recovery. • Sufficient conditions for stable recovery with RHT based on RIP and mutual coherence. • RHT achieves good recovery performance in both stimulated and real-world experiments. • RHT shows similar efficiency with IHT, and outperforms the remaining algorithms. [ABSTRACT FROM AUTHOR]