去除稀疏和结构化噪声的交替方向增强拉格朗日算法

图像和视频去噪是数字图像处理的必要环节之一.为了去除图像和视频中广泛存在的稀疏噪声和结构化噪声,提出了一种分离低秩矩阵、稀疏矩阵和结构化矩阵的优化模型一主成分离群点追求.在交替方向最小化思想的基础上,利用增强拉格朗日乘子法求解主成分离群点追求模型,设计了求解模型的交替方向增强拉格朗日(ADAL)算法,加入了一种连续技术以提高算法的收敛速率.仿真实验结果表明,提出的模型和算法能够有效去除不同尺寸矩阵的不同比例的稀疏噪声和结构化噪声.     

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

低秩矩阵恢复问题作为一类在图像处理和信号数据分析等领域中都十分重要的问题已被广泛研究.本文在交替方向算法的框架下,应用非单调技术,提出一种求解低秩矩阵恢复问题的新算法.该算法在每一步迭代过程中,首先利用一步带有变步长梯度算法同时更新低秩部分的两块变量,然后采用非单调技术更新稀疏部分的变量.在一定的假设条件下,本文证明了...     

基于ADMM正则化轨道算法的高维稀疏精度矩阵估计

考虑预测变量p的数量超过样本大小n的高维稀疏精度矩阵.近年来,由于高维稀疏精度矩阵估计变得越来越流行,所以文章专注于计算正则化路径,或者在整个正则化参数范围内解决优化问题.首先使用定义在正定性约束下最小化Lasso目标函数精度矩阵估计器,然后对稀疏精度矩阵使用乘数交替方向法(ADMM)算法正则化路径,以快速估计与正则化...     

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

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

闭凸集约束下线性矩阵方程求解的松弛交替投影算法

研究线性矩阵方程AXB=C在闭凸集合R约束下的数值迭代解法.所考虑的闭凸集合R为(1)有界矩阵集合,(2)Q-正定矩阵集合和(3)矩阵不等式解集合.构造松弛交替投影算法求解上述问题,并用算子理论证明了由该算法生成的序列具有弱收敛性.给出了矩阵方程AXB=C求对称非负解和对称半正定解的数值算例,大量数值实验验证了该算法的可行性和高效性,并说明该算法与交替投影算法和谱投影梯度算法比较在迭代效率上的明显优势.     

半监督距离度量学习内蕴加速投影梯度算法

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.     

求解矩阵方程组的ABS算法

本文基于一类线性空间(Rn,n)n,n,建立求解( )X=B形式的矩阵方程组的ABS算法.讨论基本的ABS算法和两个特殊的ABS算法及其性质.并将其中的Huang算法用于求解带有各种约束(包括对称和稀疏约束)的拟牛顿方程.     

稀疏线性规划研究

稀疏线性规划在金融计算、工业生产、装配调度等领域应用十分广泛.本文首先给出稀疏线性规划问题的一般模型并证明问题是NP困难问题;其次采用交替方向乘子法(ADMM)求解该问题;最后证明了算法在近似问题上的收敛性.数值实验表明,算法在大规模数值算例上的表现优于已有的混合遗传算法;同时通过对金融实例的计算验证了算法及模型在稀疏投资组合问题上的有效性.     

地震时频分析的加权l_1范数稀疏正则化及交替方向乘子算法

地震时频分析在地震信号处理中具有重要意义.本文研究一种基于反演的稀疏算法来对反射地震记录进行时频分析.首先使用窗口逆Fourier变换来形成正演问题,然后建立一个加权l_1范数约束的最小化模型,用于求解未知模型参数向量(Fourier频率域系数).为了实现最小化问题,本文提出应用加权交替方向乘子法(ADMM)进行求解.数值试验部分针对短时Fourier变换(STFT)、连续小波变换(CWT)和本文提出的算法进行了对比结果分析.从比较结果可以看出,本文提出的优化模型和相关算法可以得到比STFT和CWT更高分辨率的地震数据的频谱分解.     

稀疏近似逆预处理求解一类矩阵方程

本文给出一类矩阵方程的基于F-范数最小化的稀疏近似逆预处理方法.首先,运用基于F-范数最小化的稀疏近似逆技术寻求一个有效的预处理子M.然后,将得到的预处理子运用到正交投影迭代法中,得到新的算法,并证明算法的收敛性.最后,通过数值实例来验证预处理方法的有效性.     

Robust quaternion matrix completion with applications to image inpainting

In this paper, we study robust quaternion matrix completion and provide a rigorous analysis for provable estimation of quaternion matrix from a random subset of their corrupted entries. In order to generalize the results from real matrix completion to quaternion matrix completion, we derive some new formulas to handle noncommutativity of quaternions. We solve a convex optimization problem, which minimizes a nuclear norm of quaternion matrix that is a convex surrogate for the quaternion matrix rank, and the ?₁‐norm of sparse quaternion matrix entries. We show that, under incoherence conditions, a quaternion matrix can be recovered exactly with overwhelming probability, provided that its rank is sufficiently small and that the corrupted entries are sparsely located. The quaternion framework can be used to represent red, green, and blue channels of color images. The results of missing/noisy color image pixels as a robust quaternion matrix completion problem are given to show that the performance of the proposed approach is better than that of the testing methods, including image inpainting methods, the tensor‐based completion method, and the quaternion completion method using semidefinite programming.     

Blind Channel Identification Based on Noisy Observation by Stochastic Approximation Method

A stochastic approximation algorithm for estimating multichannel coefficients is proposed, and the estimate is proved to converge to the true parameters a.s. up-to a constant scaling factor. The estimate is updated after receiving each new observation, so the output data need not be collected in advance. The input signal is allowed to be dependent and the observation is allowed to be corrupted by noise, but no noise statistics are used in the estimation algorithm.     

An alternating direction algorithm for matrix completion with nonnegative factors

This paper introduces an algorithm for the nonnegative matrix factorization-and-completion problem, which aims to find nonnegative low-rank matrices X and Y so that the product XY approximates a nonnegative data matrix M whose elements are partially known (to a certain accuracy). This problem aggregates two existing problems: (i) nonnegative matrix factorization where all entries of M are given, and (ii) low-rank matrix completion where nonnegativity is not required. By taking the advantages of both nonnegativity and low-rankness, one can generally obtain superior results than those of just using one of the two properties. We propose to solve the non-convex constrained least-squares problem using an algorithm based on the classical alternating direction augmented Lagrangian method. Preliminary convergence properties of the algorithm and numerical simulation results are presented. Compared to a recent algorithm for nonnegative matrix factorization, the proposed algorithm produces factorizations of similar quality using only about half of the matrix entries. On tasks of recovering incomplete grayscale and hyperspectral images, the proposed algorithm yields overall better qualities than those produced by two recent matrix-completion algorithms that do not exploit nonnegativity.     

Dynamical reconstruction of unknown inputs in nonlinear differential equations

We present an algorithm for the identification of an unknown but bounded input to a nonlinear finite-dimensional system, based on observations taken at discrete time instants and corrupted by observation errors. This algorithm is stable with respect to observation and computational errors.If we have the further information that the unknown input is a signal of bounded variation, then we can give explicit convergence estimates of the algorithm.     

Image decoding optimization based on compressive sensing

Transform-based image codec follows the basic principle: the reconstructed quality is decided by the quantization level. Compressive sensing (CS) breaks the limit and states that sparse signals can be perfectly recovered from incomplete or even corrupted information by solving convex optimization. Under the same acquisition of images, if images are represented sparsely enough, they can be reconstructed more accurately by CS recovery than inverse transform. So, in this paper, we utilize a modified TV operator to enhance image sparse representation and reconstruction accuracy, and we acquire image information from transform coefficients corrupted by quantization noise. We can reconstruct the images by CS recovery instead of inverse transform. A CS-based JPEG decoding scheme is obtained and experimental results demonstrate that the proposed methods significantly improve the PSNR and visual quality of reconstructed images compared with original JPEG decoder.     

Image decoding optimization based on compressive sensing

Transform-based image codec follows the basic principle: the reconstructed quality is decided by the quantization level. Compressive sensing (CS) breaks the limit and states that sparse signals can be perfectly recovered from incomplete or even corrupted information by solving convex optimization. Under the same acquisition of images, if images are represented sparsely enough, they can be reconstructed more accurately by CS recovery than inverse transform. So, in this paper, we utilize a modified TV operator to enhance image sparse representation and reconstruction accuracy, and we acquire image information from transform coefficients corrupted by quantization noise. We can reconstruct the images by CS recovery instead of inverse transform. A CS-based JPEG decoding scheme is obtained and experimental results demonstrate that the proposed methods significantly improve the PSNR and visual quality of reconstructed images compared with original JPEG decoder.     

Nonlinear Stability Problem of a Rotating Doubly Diffusive Porous Layer

Lyapunov direct method is applied to study the non-linear conditional stability problem of a rotating doubly diffusive convection in a sparsely packed porous layer. For a Darcy number greater than or equal to 1000, and for any Prandtl number, Taylor number, and solute Rayleigh number it is found that the non-linear stability bound coincides with linear instability bound. For a Darcy number less than 1000, for a Prandtl number greater than or equal to one, and for a certain range of Taylor number, a coincidence between the linear and nonlinear (energy) stability thermal Rayleigh number values is still maintained. However, it is noted that for a Darcy number less than 1000, as the value of the solute Rayleigh number or the Taylor number increases, the coincidence domain between the two theories decreases quickly.     

Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations

Given a set of corrupted data drawn from a union of multiple subspace, the subspace recovery problem is to segment the data into their respective subspace and to correct the possible noise simultaneously. Recently, it is discovered that the task can be characterized, both theoretically and numerically, by solving a matrix nuclear-norm and a ?_2,1-mixed norm involved convex minimization problems. The minimization model actually has separable structure in both the objective function and constraint; it thus falls into the framework of the augmented Lagrangian alternating direction approach. In this paper, we propose and investigate an augmented Lagrangian algorithm. We split the augmented Lagrangian function and minimize the subproblems alternatively with one variable by fixing the other one. Moreover, we linearize the subproblem and add a proximal point term to easily derive the closed-form solutions. Global convergence of the proposed algorithm is established under some technical conditions. Extensive experiments on the simulated and the real data verify that the proposed method is very effective and faster than the sate-of-the-art algorithm LRR.     

A Constrained Optimization Approach for LCP

In this paper, LCP is converted to an equivalent nonsmooth nonlinear equation system H(x,y) = 0 by using the famous NCP function-Fischer-Burmeister function. Note that some equations in H(x, y) = 0 are nonsmooth and nonlinear hence difficult to solve while the others are linear hence easy to solve. Then we further convert the nonlinear equation system H(x, y) = 0 to an optimization problem with linear equality constraints. After that we study the conditions under which the K-T points of the optimization problem are the solutions of the original LCP and propose a method to solve the optimization problem. In this algorithm, the search direction is obtained by solving a strict convex programming at each iterative point, However, our algorithm is essentially different from traditional SQP method. The global convergence of the method is proved under mild conditions. In addition, we can prove that the algorithm is convergent superlinearly under the conditions: M is P0 matrix and the limit point is a strict complementarity solution of LCP. Preliminary numerical experiments are reported with this method.     

A Sparse Singular Value Decomposition Method for High-Dimensional Data

We present a new computational approach to approximating a large, noisy data table by a low-rank matrix with sparse singular vectors. The approximation is obtained from thresholded subspace iterations that produce the singular vectors simultaneously, rather than successively as in competing proposals. We introduce novel ways to estimate thresholding parameters, which obviate the need for computationally expensive cross-validation. We also introduce a way to sparsely initialize the algorithm for computational savings that allow our algorithm to outperform the vanilla singular value decomposition (SVD) on the full data table when the signal is sparse. A comparison with two existing sparse SVD methods suggests that our algorithm is computationally always faster and statistically always at least comparable to the better of the two competing algorithms. Supplementary materials for the article are available in an online appendix. An R package ssvd implementing the algorithms introduced in this article is available on CRAN.