基于l1-l2范数的块稀疏信号重构

压缩感知(compressed sensing,CS) 是一种全新的信息采集与处理的理论框架,借助信号内在的稀疏性或可压缩性,可以从小规模的线性、非自适应的测量中通过求解非线性优化问题重构原信号.块稀疏信号是一种具有块结构的信号,即信号的非零元是成块出现的.受YIN Peng-hang, LOU Yi-fei, HE Qi等提出的l_1-2范数最小化方法的启发,将基于l₁-l₂范数的稀疏重构算法推广到块稀疏模型,证明了块稀疏模型下l₁-l₂范数的相关性质,建立了基于l₁-l₂范数的块稀疏信号精确重构的充分条件,并通过DCA(difference of convex functions algorithm) 和ADMM(alternating direction method of multipliers)给出了求解块稀疏模型下l₁-l₂范数的迭代方法.数值实验表明,基于l₁-l₂范数的块稀疏重构算法比其他块稀疏重构算法具有更高的重构成功率.     

加权再生核空间中信号的平均采样与重构

主要讨论L_v~p的加权再生核子空间中信号的平均采样与重构.首先,针对两种平均采样泛函建立了采样稳定性;其次,基于概率测度给出一个一般的迭代算法,将迭代逼近投影算法和迭代标架算法统一起来;最后,针对被白噪声污染的平均样本给出了信号重构的渐进点态误差估计.     

基于新的Hessian近似矩阵的稀疏重构算法

一般来说,基于二次近似模型的优化算法具有良好的数值表现.然而,当基于二次近似模型的优化算法求解大规模优化问题时,若使用稠密矩阵近似目标函数在迭代点的Hessian矩阵,需要花费大量的计算成本和存储成本,因此设计Hessian矩阵合适的标量近似矩阵特别重要.对于正则化模型,利用最近三次迭代的信息,设计粗糙的标量矩阵,使用拟牛顿公式进行更新,结合近似最优梯度法的思想和梯度法的延迟策略,构造Hessian矩阵新的含有更多二阶信息的标量近似矩阵.结合非单调线搜索,提出基于新的Hessian近似矩阵的稀疏重构算法,并进行收敛性分析.实验结果表明,与经典稀疏重构算法算法相比,基于新的Hessian近似矩阵的稀疏重构算法在重构效果相似的情况下能较大地减少迭代次数和较快地重构信号.     

基于左截断右删失数据的单参数Pareto分布参数估计

基于EM算法及极大似然法研究了左截断右删失数据下单参数Pareto分布的参数估计,导出其迭代式,并应用随机模拟对参数估计式进行了模拟检验,结果表明迭代式能够快速收敛,EM估计值较为精确.     

基于MINRES-QLP截断牛顿法的全波形反演

在全波形反演过程中,二阶梯度信息扮演着重要的作用.然而,由于其巨大的计算量和内存需求,限制了其在全波形反演问题中的应用.本文基于MINRES-QLP方法提出了一种高效的截断牛顿全波形反演方法.该全波形反演方法能够充分利用目标泛函的二阶梯度信息,提高反演精度.MINRES-QLP反演方法还能够利用Hessian阵负特征值信息,从而提高算法的重构分辨率和计算效率.针对Hessian阵计算难题,本文给出了一种矩阵向量相乘的快速算法.基于二维2004 BP模型,Sigsbee模型,验证了MINRES-QLP截断牛顿反演方法的有效性.数值结果表明MINRES-QLP截断牛顿法能充分利用二阶梯度信息和Hessian阵负特征值信息,从而加速算法收敛速度和提高成像精度.     

加权无标度网络中的疾病传播

提出具有加权传播率和非线性传染能力的SIR模型和SIS模型,通过平均场方法证明了这两个模型在加权无标度网络中可以存在非零的传播阈值,从而传播率需要跨越更大的传播阈值才能流行.并且得到的结果在特殊情况下可退化为已有的一些经典结论.     

求解l1极小化问题的Bregman迭代算法

在Tikhonov正则化方法的基础上将其转化为一类l1极小化问题进行求解,并基于Bregman迭代正则化构建了Bregman迭代算法,实现了l1极小化问题的快速求解.数值实验结果表明,Bregman迭代算法在快速求解算子方程的同时,有着比最小二乘法和Tikhonov正则化方法更高的求解精度.     

一种求解弹性l_2-l_q正则化问题的算法

给出了一种求解弹性l_{2}-l_{q}正则化问题的迭代重新加权l_{1}极小化算法, 并证明了由该算法产生的迭代序列是有界且渐进正则的. 对于任何有理数q\in(0,1), 基于一个代数的方法, 进一步证明了迭代重新加权l_{1}极小化算法收敛到弹性l_{2}-l_{q}(0相似文献   

参量离散代数Riccati方程对称解的两类迭代算法

基于求线性矩阵方程约束解的修正共轭梯度法,针对源于低增益反馈设计和时滞控制系统中的一类参量离散代数Riccati方程,建立求其非零对称解的Newton-MCG算法和非精确Newton-MCG算法以及求其可逆对称解的T-MCG算法.(非精确)Newton-MCG算法仅要求Riccati方程存在非零对称解,对系数矩阵等没有附加限定,但所得对称解不能保证可逆性或正定性;在系数矩阵满足可控性等条件下,由T-MCG算法所得对称解是正定的.数值算例表明,两类迭代算法是有效的.     

求解低秩矩阵填充的改进的交替最速下降法

矩阵填充是指利用矩阵的低秩特性而由部分观测元素恢复出原矩阵,在推荐系统、信号处理、医学成像、机器学习等领域有着广泛的应用。采用精确线搜索的交替最速下降法由于每次迭代计算量小因而对大规模问题的求解非常有效。本文在其基础上采用分离地精确线搜索,可使得每次迭代下降更多但计算量相同,从而可望进一步提高计算效率。本文分析了新算法的收敛性。数值结果也表明所提出的算法更加有效。     

Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit

This paper seeks to bridge the two major algorithmic approaches to sparse signal recovery from an incomplete set of linear measurements—L₁-minimization methods and iterative methods (Matching Pursuits). We find a simple regularized version of Orthogonal Matching Pursuit (ROMP) which has advantages of both approaches: the speed and transparency of OMP and the strong uniform guarantees of L₁-minimization. Our algorithm, ROMP, reconstructs a sparse signal in a number of iterations linear in the sparsity, and the reconstruction is exact provided the linear measurements satisfy the uniform uncertainty principle.      

Convergence of the reweighted ℓ 1 minimization algorithm for ℓ 2–ℓ p minimization

The iteratively reweighted ? ₁ minimization algorithm (IRL1) has been widely used for variable selection, signal reconstruction and image processing. In this paper, we show that any sequence generated by the IRL1 is bounded and any accumulation point is a stationary point of the ? ₂–? _p minimization problem with 0<p<1. Moreover, the stationary point is a global minimizer and the convergence rate is approximately linear under certain conditions. We derive posteriori error bounds which can be used to construct practical stopping rules for the algorithm.     

Convergence and error estimate of cascade algorithms with infinitely supported masks in L p (? s )

The cascade algorithm plays an important role in computer graphics and wavelet analysis.In this paper,we first investigate the convergence of cascade algorithms associated with a polynomially decaying mask and a general dilation matrix in L p (R s) (1 p ∞) spaces,and then we give an error estimate of the cascade algorithms associated with truncated masks.It is proved that under some appropriate conditions if the cascade algorithm associated with a polynomially decaying mask converges in the L p-norm,then the cascade algorithms associated with the truncated masks also converge in the L p-norm.Moreover,the error between the two resulting limit functions is estimated in terms of the masks.     

Landweber iterative methods for angle-limited image reconstruction

We introduce a general iterative scheme for angle-limited image reconstruction based on Landwebet＇s method. We derive a representation formula for this scheme and consequently establish its convergence conditions. Our results suggest certain relaxation strategies for an accelerated convergence for angle-limited image reconstruction in L^2-norm comparing with alternative projection methods. The convolution-backprojection algorithm is given for this iterative process.     

Parametric target detection algorithm based on ISLIM for hyperspectral imaging

A supervised subpixel target detection algorithm based on iterative simple linear model for hyperspectral imaging is developed. Parameter estimation, whitening transformation, and comparison of the test results with the classical approach are discussed. Numerical results indicate that the performance of the parametric algorithm is comparable with the corresponding classical approach and requires fewer training pixels.     

A splitting primal-dual proximity algorithm for solving composite optimization problems

Our work considers the optimization of the sum of a non-smooth convex function and a finite family of composite convex functions, each one of which is composed of a convex function and a bounded linear operator. This type of problem is associated with many interesting challenges encountered in the image restoration and image reconstruction fields. We developed a splitting primal-dual proximity algorithm to solve this problem. Furthermore, we propose a preconditioned method, of which the iterative parameters are obtained without the need to know some particular operator norm in advance. Theoretical convergence theorems are presented. We then apply the proposed methods to solve a total variation regularization model, in which the L2 data error function is added to the L1 data error function. The main advantageous feature of this model is its capability to combine different loss functions. The numerical results obtained for computed tomography (CT) image reconstruction demonstrated the ability of the proposed algorithm to reconstruct an image with few and sparse projection views while maintaining the image quality.     

Univariate cubic L 1 interpolating splines based on the first derivative and on 5-point windows: analysis, algorithm and shape-preserving properties

In this paper, univariate cubic L ₁ interpolating splines based on the first derivative and on 5-point windows are introduced. Analytical results for minimizing the local spline functional on 5-point windows are presented and, based on these results, an efficient algorithm for calculating the spline coefficients is set up. It is shown that cubic L ₁ splines based on the first derivative and on 5-point windows preserve linearity of the original data and avoid extraneous oscillation. Computational examples, including comparison with first-derivative-based cubic L ₁ splines calculated by a primal affine algorithm and with second-derivative-based cubic L ₁ splines, show the advantages of the first-derivative-based cubic L ₁ splines calculated by the new algorithm.     

Anomalous behavior in bin packing algorithms

In the classical bin packing problem one is given a list of items and asked to pack them into the fewest possible unit-sized bins. Given two lists, L₁ and L₂, where L₂ is derived from L₁ by deleting some elements of L₁ and/or reducing the size of some elements of L₁, one might hope that an approximation algorithm would use no more bins to pack L₂ than it uses to pack L₁. Johnson and Graham have given examples showing that First-Fit and First-Fit Decreasing can actually use more bins to pack L₂ than L₁. Graham has also studied this type of behavior among multiprocessor scheduling algorithms. In the present paper we extend this study of anomalous behavior to a broad class of approximation algorithms for bin packing. To do this we introduce a technique which allows one to characterize the monotonic/anomalous behavior of any algorithm in a large, natural class. We then derive upper and lower bounds on the anomalous behavior of the algorithms which are anomalous and provide conditions under which a normally nonmonotonic algorithm becomes monotonic.     

Enhancing Sparsity by Reweighted ℓ 1 Minimization

It is now well understood that (1) it is possible to reconstruct sparse signals exactly from what appear to be highly incomplete sets of linear measurements and (2) that this can be done by constrained ? ₁ minimization. In this paper, we study a novel method for sparse signal recovery that in many situations outperforms ? ₁ minimization in the sense that substantially fewer measurements are needed for exact recovery. The algorithm consists of solving a sequence of weighted ? ₁-minimization problems where the weights used for the next iteration are computed from the value of the current solution. We present a series of experiments demonstrating the remarkable performance and broad applicability of this algorithm in the areas of sparse signal recovery, statistical estimation, error correction and image processing. Interestingly, superior gains are also achieved when our method is applied to recover signals with assumed near-sparsity in overcomplete representations—not by reweighting the ? ₁ norm of the coefficient sequence as is common, but by reweighting the ? ₁ norm of the transformed object. An immediate consequence is the possibility of highly efficient data acquisition protocols by improving on a technique known as Compressive Sensing.     

Sparsity reconstruction in electrical impedance tomography: An experimental evaluation

We investigate the potential of sparsity constraints in the electrical impedance tomography (EIT) inverse problem of inferring the distributed conductivity based on boundary potential measurements. In sparsity reconstruction, inhomogeneities of the conductivity are a priori assumed to be sparse with respect to a certain basis. This prior information is incorporated into a Tikhonov-type functional by including a sparsity-promoting ?¹-penalty term. The functional is minimized with an iterative soft shrinkage-type algorithm. In this paper, the feasibility of the sparsity reconstruction approach is evaluated by experimental data from water tank measurements. The reconstructions are computed both with sparsity constraints and with a more conventional smoothness regularization approach. The results verify that the adoption of ?¹-type constraints can enhance the quality of EIT reconstructions: in most of the test cases the reconstructions with sparsity constraints are both qualitatively and quantitatively more feasible than that with the smoothness constraint.