Sharp Recovery Bounds for Convex Demixing,with Applications

Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model that ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (1) demixing two signals that are sparse in mutually incoherent bases, (2) decoding spread-spectrum transmissions in the presence of impulsive errors, and (3) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.     

A modified greedy analysis pursuit algorithm for the cosparse analysis model

In the past decade, the sparse representation synthesis model has been deeply researched and widely applied in signal processing. Recently, a cosparse analysis model has been introduced as an interesting alternative to the sparse representation synthesis model. The sparse synthesis model pay attention to non-zero elements in a representation vector x, while the cosparse analysis model focuses on zero elements in the analysis representation vector Ωx. This paper mainly considers the problem of the cosparse analysis model. Based on the greedy analysis pursuit algorithm, by constructing an adaptive weighted matrix W _k?1, we propose a modified greedy analysis pursuit algorithm for the sparse recovery problem when the signal obeys the cosparse model. Using a weighted matrix, we fill the gap between greedy algorithm and relaxation techniques. The standard analysis shows that our algorithm is convergent. We estimate the error bound for solving the cosparse analysis model, and then the presented simulations demonstrate the advantage of the proposed method for the cosparse inverse problem.     

低秩稀疏矩阵恢复的快速非单调交替极小化方法

针对低秩稀疏矩阵恢复问题的一个非凸优化模型,本文提出了一种快速非单调交替极小化方法.主要思想是对低秩矩阵部分采用交替极小化方法,对稀疏矩阵部分采用非单调线搜索技术来分别进行迭代更新.非单调线搜索技术是将单步下降放宽为多步下降,从而提高了计算效率.文中还给出了新算法的收敛性分析.最后,通过数值实验的比较表明,矩阵恢复的非单调交替极小化方法比原单调类方法更有效.     

Optimized projections for compressed sensing via rank-constrained nearest correlation matrix

Optimizing the acquisition matrix is useful for compressed sensing of signals that are sparse in overcomplete dictionaries, because the acquisition matrix can be adapted to the particular correlations of the dictionary atoms. In this paper a novel formulation of the optimization problem is proposed, in the form of a rank-constrained nearest correlation matrix problem. Furthermore, improvements for three existing optimization algorithms are introduced, which are shown to be particular instances of the proposed formulation. Simulation results show notable improvements and superior robustness in sparse signal recovery.     

Approximate factoring of the inverse

Computation of approximate factors for the inverse constitutes an algebraic approach to preconditioning large and sparse linear systems. In this paper, the aim is to combine standard preconditioning ideas with sparse approximate inverse approximation, to have dense approximate inverse approximations (implicitly). For optimality, the approximate factoring problem is associated with a minimization problem involving two matrix subspaces. This task can be converted into an eigenvalue problem for a Hermitian positive semidefinite operator whose smallest eigenpairs are of interest. Because of storage and complexity constraints, the power method appears to be the only admissible algorithm for devising sparse–sparse iterations. The subtle issue of choosing the matrix subspaces is addressed. Numerical experiments are presented.     

Interior point methods specialized to optimal pump operation costs of water distribution networks

In the water distribution problem the loss is important and the objective function must consider it combined with pump costs. The problem becomes complex because the loss in each branch is as a nonlinear function of water outflow. The objective of this work consists in solving the water distribution problem using interior point methods and to exploit the particular structure of the problem and the specific matrix sparse pattern of the of the resulting linear systems. The interior point methods show to be robust, achieving fast convergence in all instances tested. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

On structure-oriented hybrid two-stage iteration methods for the large and sparse blocked system of linear equations

In this paper, we first present a class of structure-oriented hybrid two-stage iteration methods for solving the large and sparse blocked system of linear equations, as well as the saddle point problem as a special case. And the new methods converge to the solution under suitable restrictions, for instance, when the coefficient matrix is positive stable matrix generally. Numerical experiments for a model generalized saddle point problem are given, and the results show that our new methods are feasible and efficient, and converge faster than the Classical Uzawa Method.     

On symbolic factorization of partitioned sparse symmetric matrices

Partitioning a sparse matrix A is a useful device employed by a number of sparse matrix techniques. An important problem that arises in connection with some of these methods is to determine the block structure of the Cholesky factor L of A, given the partitioned A. For the scalar case, the problem of determining the structure of L from A, so-called symbolic factorization, has been extensively studied. In this paper we study the generalization of this problem to the block case. The problem is interesting because an assumption relied on in the scalar case no longer holds; specifically, the product of two nonzero scalars is always nonzero, but the product of two nonnull sparse matrices may yield a zero matrix. Thus, applying the usual symbolic factorization techniques to a partitioned matrix, regarding each submatrix as a scalar, may yield a block structure of L which is too full. In this paper an efficient algorithm is provided for determining the block structure of the Cholesky factor of a partitioned matrix A, along with some bounds on the execution time of the algorithm.     

Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods

We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as \(\ell _1\_\ell _s\) and Mirror Prox regardless of the sparsity level or problem size.     

Solving the eigenvalue problem for sparse matrices

A modification of the Danilewski method is presented, permitting the solution of the eigenvalue problem for a constant sparse matrix of large order to be reduced to the solution of the same problem for a polynomial matrix of lower order. Certain solution algorithms are proposed for a partial eigenvalue problem for the polynomial matrix. Questions of the realization of the algorithms on a model PRORAB computer are examined.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 92–110, 1976.     

Sparse principal component analysis via regularized low rank matrix approximation

Principal component analysis (PCA) is a widely used tool for data analysis and dimension reduction in applications throughout science and engineering. However, the principal components (PCs) can sometimes be difficult to interpret, because they are linear combinations of all the original variables. To facilitate interpretation, sparse PCA produces modified PCs with sparse loadings, i.e. loadings with very few non-zero elements. In this paper, we propose a new sparse PCA method, namely sparse PCA via regularized SVD (sPCA-rSVD). We use the connection of PCA with singular value decomposition (SVD) of the data matrix and extract the PCs through solving a low rank matrix approximation problem. Regularization penalties are introduced to the corresponding minimization problem to promote sparsity in PC loadings. An efficient iterative algorithm is proposed for computation. Two tuning parameter selection methods are discussed. Some theoretical results are established to justify the use of sPCA-rSVD when only the data covariance matrix is available. In addition, we give a modified definition of variance explained by the sparse PCs. The sPCA-rSVD provides a uniform treatment of both classical multivariate data and high-dimension-low-sample-size (HDLSS) data. Further understanding of sPCA-rSVD and some existing alternatives is gained through simulation studies and real data examples, which suggests that sPCA-rSVD provides competitive results.     

A GREEDY ALGORITHM FOR SPARSE PRECISION MATRIX APPROXIMATION

Precision matrix estimation is an important problem in statistical data analysis.This paper proposes a sparse precision matrix estimation approach,based on CLIME estimator and an efficient algorithm GISSρ that was originally proposed for l1 sparse signal recov-ery in compressed sensing.The asymptotic convergence rate for sparse precision matrix estimation is analyzed with respect to the new stopping criteria of the proposed GISSρ algorithm.Finally,numerical comparison of GISSρ with other sparse recovery algorithms,such as ADMM and HTP in three settings of precision matrix estimation is provided and the numerical results show the advantages of the proposed algorithm.     

张量鲁棒主成分分析的增广拉格朗日交替方向方法

张量的鲁棒主成分分析是将未知的一个低秩张量与一个稀疏张量从已知的它们的和中分离出来.因为在计算机视觉与模式识别中有着广阔的应用前景,该问题在近期成为学者们的研究热点.本文提出了一种针对张量鲁棒主成分分析的新的模型,并给出交替方向极小化的求解算法,在求解过程中给出了两种秩的调整策略.针对低秩分量本文对其全部各阶展开矩阵进行低秩矩阵分解,针对稀疏分量采用软阈值收缩的策略.无论目标低秩张量为精确低秩或近似低秩,本文所提方法均可适用.本文对算法给出了一定程度上的收敛性分析,即算法迭代过程中产生的任意收敛点均满足KKT条件.如果目标低秩张量为精确低秩,当迭代终止时可对输出结果进行基于高阶奇异值分解的修正.针对人工数据和真实视频数据的数值实验表明,与同类型算法相比,本文所提方法可以得到更好的结果.     

求解低秩矩阵恢复问题的非单调交替梯度方向法

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了新算法的全局收敛性.最后通过解决随机低秩矩阵恢复问题和视频前景背景分离的实例验证新算法的有效性,同时也显示非单调技术极大改善了算法的效率.     

Fixed-size Least Squares Support Vector Machines: A Large Scale Application in Electrical Load Forecasting

Based on the Nyström approximation and the primal-dual formulation of the least squares support vector machines, it becomes possible to apply a nonlinear model to a large scale regression problem. This is done by using a sparse approximation of the nonlinear mapping induced by the kernel matrix, with an active selection of support vectors based on quadratic Renyi entropy criteria. The methodology is applied to the case of load forecasting as an example of a real-life large scale problem in industry. The forecasting performance, over ten different load series, shows satisfactory results when the sparse representation is built with less than 3% of the available sample.     

Direct solution method for the equilibrium problem for elastic stents

We are interested in numerical methods for approximating vector‐valued functions on a metric graph. As a model problem, we formulate and analyze a numerical method for the solution of the stationary problem for the one‐dimensional elastic stent model. The approximation is built using the mixed finite element method. The discretization matrix is a symmetric saddle‐point matrix, and we discuss sparse direct methods for the fast and robust solution of the associated equilibrium system. The convergence of the numerical method is proven and the error estimate is obtained. Numerical examples confirm the theoretical estimates.     

Efficient algorithms for robust and stable principal component pursuit problems

The problem of recovering a low-rank matrix from a set of observations corrupted with gross sparse error is known as the robust principal component analysis (RPCA) and has many applications in computer vision, image processing and web data ranking. It has been shown that under certain conditions, the solution to the NP-hard RPCA problem can be obtained by solving a convex optimization problem, namely the robust principal component pursuit (RPCP). Moreover, if the observed data matrix has also been corrupted by a dense noise matrix in addition to gross sparse error, then the stable principal component pursuit (SPCP) problem is solved to recover the low-rank matrix. In this paper, we develop efficient algorithms with provable iteration complexity bounds for solving RPCP and SPCP. Numerical results on problems with millions of variables and constraints such as foreground extraction from surveillance video, shadow and specularity removal from face images and video denoising from heavily corrupted data show that our algorithms are competitive to current state-of-the-art solvers for RPCP and SPCP in terms of accuracy and speed.     

Implementación eficiente de una formulación semirrecursiva para la dinámica de sistemas multicuerpo de gran tamaño

This article shows an efficient implementation of a dynamic semi-recursive formulation for large and complex multibody system simulations, with interesting applications in the automotive field and especially with industrial vehicles. These systems tend to have a huge amount of kinematic constraints, becoming usual the presence of redundant but compatible systems of equations. The maths involved in the solution of these problems have a high computational cost, making very challenging to achieve real-time simulations.In this article, two implementations to increase the efficiency of these computations will be shown. The difference between them is the way they consider the Jacobian matrix of the constraint equations. The first one treats this matrix as a dense one, using the BLAS functions to solve the system of equations. The second one takes into account the sparse pattern of the Jacobian matrix, introducing the sparse function MA48 from Harwell.Both methodologies have been applied on two multibody system models with different sizes. The first model is a vehicle IVECO DAILY 35C15 with 17 degrees of freedom. The second one is a semi-trailer truck with 40 degrees of freedom. Taking as a reference the standard C/C + + implementation, the efficiency improvements that have been achieved using dense matrices (BLAS) have been of 15% and 50% respectively. The results in the first model have not improved significantly by using sparse matrices, but in the second one, the times with sparse matrices have been reduced 8% with respect to the BLAS ones.     

Numerical solution of the acoustic wave equation using Raviart–Thomas elements

In this paper we discuss the numerical approximation of the displacement form of the acoustic wave equation using mixed finite elements. The mixed formulation allows for approximation of both displacement and pressure at each time step, without the need for post-processing. Lowest-order and next-to-lowest-order Raviart–Thomas elements are used for the spatial discretization, and centered finite differences are used to advance in time. Use of these Raviart–Thomas elements results in a diagonal mass matrix for resolution of pressure, and a mass matrix for the displacement variable that is sparse with a simple structure. Convergence results for a model problem are provided, as are numerical results for a two-dimensional problem with a point source.