Necessary and Sufficient Convergence Conditions for Algebraic Image Reconstruction Algorithms

The Landweber scheme is an algebraic reconstruction method and includes several important algorithms as its special cases. The convergence of the Landweber scheme is of both theoretical and practical importance. Using the singular value decomposition (SVD), we derive an iterative representation formula for the Landweber scheme and consequently establish the necessary and sufficient conditions for its convergence. In addition to verifying the necessity and sufficiency of known convergent conditions, we find new convergence conditions allowing relaxation coefficients in an interval not covered by known results. Moreover, it is found that the Landweber scheme can converge within finite iterations when the relaxation coefficients are chosen to be the inverses of squares of the nonzero singular values. Furthermore, the limits of the Landweber scheme in all convergence cases are shown to be the sum of the minimum norm solution of a weighted least-squares problem and an oblique projection of the initial image onto the null space of the system matrix.     

Numerical study of multigrid implementations of some iterative image reconstruction algorithms

The numerical behavior of multigrid implementations of the Landweber, generalized Landweber, ART, and MLEM iterative image reconstruction algorithms is investigated. Comparisons between these algorithms, and with their single-grid implementations, are made on two small-scale synthetic PET systems, for phantom objects exhibiting different characteristics, and on one full-scale synthetic system, for a Shepp-Logan phantom. The authors also show analytically the effects of noise and initial condition on the generalized Landweber iteration, and note how to choose the shaping operator to filter out noise in the data, or to enhance features of interest in the reconstructed image. Original contributions include (1) numerical studies of the convergence rates of single-grid and multigrid implementations of the Landweber, generalized Landweber, ART, and MLEM iterations and (2) effects of noise and initial condition on the generalized Landweber iteration, with procedures for filtering out noise or enhancing image features     

Acceleration and filtering in the generalized Landweber iteration using a variable shaping matrix

The generalized Landweber iteration with a variable shaping matrix is used to solve the large linear system of equations arising in the image reconstruction problem of emission tomography. The method is based on the property that once a spatial frequency image component is almost recovered within in in the generalized Landweber iteration, this component will still stay within in during subsequent iterations with a different shaping matrix, as long as this shaping matrix satisfies the convergence criterion for the component. Two different shaping matrices are used: the first recovers low-frequency image components; and the second may be used either to accelerate the reconstruction of high-frequency image components, or to attenuate these components to filter the image. The variable shaping matrix gives results similar to truncated inverse filtering, but requires much less computation and memory, since it does not rely on the singular value decomposition.     

语音重构的DCT域加速Landweber迭代硬阈值算法

重构信号的最基本理论依据是该信号在某个变换域是稀疏的或近似稀疏的。基于语音信号在DCT域的近似稀疏性,可以采用压缩感知(Compressed Sensing, CS)理论对其进行重构。压缩感知理论中的迭代硬阈值(Iterative hard thresholding, IHT)算法以其较好的性能被广泛用来重构信号,但其收敛速度比较慢,如何提高收敛速度,一直是迭代硬阈值算法研究的重点之一。针对压缩感知理论中的IHT算法收敛速度相当慢的问题,提出了语音重构的DCT域加速Landweber迭代硬阈值(Accelerated Landweber iterative hard thresholding, ALIHT)算法。该算法对原始语音信号做DCT变换,然后在DCT域将每一步Landweber迭代分解为矩阵计算和求解两步,通过修改其中的矩阵计算部分实现Landweber迭代加速,最后通过迭代硬阈值对信号做阈值处理。实验结果表明,加速Landweber迭代硬阈值算法加快了收敛速度、减少了计算量。      

A Balanced Approach to Multichannel Blind Deconvolution

In some general state-space approaches to the multichannel blind deconvolution problem, e.g., the information backpropagation approach (Zhang and Cichocki 2000), an implicit assumption is usually involved therein, viz., the dimension of the state vector of the mixer is known a priori. In general, if the number of states in the state space is not known a priori, Zhang and Cichocki (2000) suggested using a maximum possible number of states; this procedure will introduce additional delays in the recovered source signals. In this paper, our aim is to relax this assumption. The objective is achieved by using balanced parameterization of the underlying discrete-time dynamical system. Since there are no known balanced parameterization algorithms for discrete-time systems, we need to go through a "circuitous" route, by first transforming the discrete-time system into a continuous-time system using a bilinear transformation, perform the balanced parameterization on the resulting continuous-time system, and then transform the resulting system back to discrete-time balanced parameterized system using an inverse bilinear transformation. The number of states can be determined by the number of significant singular values in the ensuing singular value decomposition step in the balanced parameterization.     

High Order Algorithms for Adaptive Filters

Faster convergence of adaptive filters has been of particular interest in the areas of adaptive equalizers and adaptive antennas. The algorithm most frequently suggested is some variation of the firstorder gradient-descent LMS algorithm. This paper investigates a general procedure for the design of higher-order algorithms. Convergence of the mean weight vector and the variance is compared for three typical algorithms. Results indicate that high order convergence of the mean weight vector can easily be achieved, and this in itself can be useful. However, the variance response of the high order algorithms can tend to have an offsetting effect which may preclude their use in some applications.     

Robust zero-watermark algorithms based on numerical relationship between adjacent blocks

In this paper, three robust zero-watermark algorithms named Direct Current coefficient RElationship (DC-RE), CUmulant combined Singular Value Decomposition (CU-SVD), and CUmulant combined Singular Value Decomposition RElationship (CU-SVD-RE) are proposed. The algorithm DC-RE gets the feature vector from the relationship of DC coefficients between adjacent blocks, CU-SVD gets the feature vector from the singular value of third-order cumulants, while CU-SVD-RE combines the essence of the first two algorithms. Specially, CU-SVD-RE gets the feature vector from the relationship between singular values of third-order cumulants. Being a cross-over studying field of watermarking and cryptography, the zero-watermark algorithms are robust without modifying the carrier. Numerical simulation obviously shows that, under geometric attacks, the performance of CU-SVD-RE and DC-RE algorithm are better and all three proposed algorithms are robust to various attacks, such as median filter, salt and pepper noise, and Gaussian low-pass filter attacks.     

Two-dimensional singular vector elements for finite-elementanalysis

The finite-element method (FEM) exhibits a reduced convergence rate when used for the analysis of geometries containing sharp edges where the electromagnetic field is singular. The convergence of the method can be-improved by introducing singular elements that model analytically predicted singular behavior. A number of authors have developed singular elements that are compatible with the scalar FEM. In this paper, we propose a new singular element that is compatible with edge-based vector finite elements and can cope with any order of singularity while preserving the sparsity of the FEM equations. Edge-based singular elements more correctly model singular fields and thus require fewer unknowns, while avoiding the introduction of spurious modes in the numerical solution. Numerical results verify that the convergence of the FEM is significantly improved     

一种广义主成分提取算法及其收敛性分析

广义主成分分析在现代信号处理的诸多领域发挥着重要的作用。目前,自适应广义主成分分析算法还并不多见。针对这一现状,该文提出一种快速收敛的广义主成分分析算法,并通过理论分析所提算法的确定性离散时间系统,导出了保证算法收敛的学习因子和初始权向量模值等边界条件。仿真实验和实际应用验证了所提算法的正确性和有用性。仿真结果还表明,所提算法比现有同类算法具有更快的收敛速度和更高的估计精度。     

Interference Avoidance and Multiaccess Vector Channels

In this paper we present application of interference avoidance in the context of a general multiple access vector channel model. We show that this monotonically increases sum capacity, and discuss algorithms for code division multiple access (CDMA) codeword optimization based on this procedure. A greedy interference avoidance algorithm for multiaccess vector channels is presented in the paper, for which we discuss convergence to a class of codeword ensembles that satisfy a simultaneous water filling solution and maximize sum capacity. Numerical results obtained from simulations that corroborate our analytical results are also presented.     

Fast and Stable Subspace Tracking

We consider the problem of adaptive subspace tracking, when the rank of the subspace we seek to estimate is assumed to be known. Starting from the data projection method (DPM), which constitutes a simple and reliable means for adaptively estimating and tracking subspaces, we develop a fast and numerically robust implementation of DPM, which comes at a considerably lower computational cost. Most existing schemes track subspaces corresponding either to the largest or to the smallest singular values, while our DPM version can switch from one subspace type to the other with a simple change of sign of its single parameter. The proposed algorithm provides orthonormal vector estimates of the subspace basis that are numerically stable since they do not accumulate roundoff errors. In fact, our scheme constitutes the first numerically stable, low complexity, algorithm for tracking subspaces corresponding to the smallest singular values. Regarding convergence towards orthonormality our scheme exhibits the fastest speed among all other subspace tracking algorithms of similar complexity.     

Recursive total least squares algorithm for single-user blindchannel equalisation

The problem of blind channel identification/equalisation using second-order statistics or equivalent deterministic properties of the oversampled channel output has attracted considerable attention. Deterministic blind subspace algorithms are particularly attractive because of their finite sample convergence property and because their solution can be obtained in closed form. Most subspace algorithms developed up until now, however, are based on block processing and have high computational and memory requirements. In the paper, adaptive techniques are used to lower the computational burden. A single-user direct symbol estimation algorithm is presented. The first step in the algorithm consists of an adaptive matrix singular value decomposition for a (virtual) channel identification-type operation. A recursive total least squares algorithm is then used to recover the input symbols. The algorithm is able to track time-varying channels     

The MIMO Iterative Waterfilling Algorithm

This paper considers the noncooperative maximization of mutual information in the vector Gaussian interference channel in a fully distributed fashion via game theory. This problem has been widely studied in a number of works during the past decade for frequency-selective channels, and recently for the more general multiple-input multiple-output (MIMO) case, for which the state-of-the art results are valid only for nonsingular square channel matrices. Surprisingly, these results do not hold true when the channel matrices are rectangular and/or rank deficient matrices. The goal of this paper is to provide a complete characterization of the MIMO game for arbitrary channel matrices, in terms of conditions guaranteeing both the uniqueness of the Nash equilibrium and the convergence of asynchronous distributed iterative waterfilling algorithms. Our analysis hinges on new technical intermediate results, such as a new expression for the MIMO waterfilling projection valid (also) for singular matrices, a mean-value theorem for complex matrix-valued functions, and a general contraction theorem for the multiuser MIMO watefilling mapping valid for arbitrary channel matrices. The quite surprising result is that uniqueness/convergence conditions in the case of tall (possibly singular) channel matrices are more restrictive than those required in the case of (full rank) fat channel matrices. We also propose a modified game and algorithm with milder conditions for the uniqueness of the equilibrium and convergence, and virtually the same performance (in terms of Nash equilibria) of the original game.     

Improved approximate QR-LS algorithms for adaptive filtering

This paper studies a class of O(N) approximate QR-based least squares (A-QR-LS) algorithm recently proposed by Liu in 1995. It is shown that the A-QR-LS algorithm is equivalent to a normalized LMS algorithm with time-varying stepsizes and element-wise normalization of the input signal vector. It reduces to the QR-LMS algorithm proposed by Liu et al. in 1998, when all the normalization constants are chosen as the Euclidean norm of the input signal vector. An improved transform-domain approximate QR-LS (TA-QR-LS) algorithm, where the input signal vector is first approximately decorrelated by some unitary transformations before the normalization, is proposed to improve its convergence for highly correlated signals. The mean weight vectors of the algorithms are shown to converge to the optimal Wiener solution if the weighting factor w of the algorithm is chosen between 0 and 1. New Givens rotations-based algorithms for the A-QR-LS, TA-QR-LS, and the QR-LMS algorithms are proposed to reduce their arithmetic complexities. This reduces the arithmetic complexity by a factor of 2, and allows square root-free versions of the algorithms be developed. The performances of the various algorithms are evaluated through computer simulation of a system identification problem and an acoustic echo canceller.     

Diffraction of plane waves by a finite array of dielectric-loaded cavity-backed slots on a common ground plane for oblique incidence and arbitrary polarization

Plane-wave diffraction by a finite array of two-dimensional dielectric-loaded cavity-backed slots on a common ground plane is investigated for oblique incidence and arbitrary polarization. The governing system of coupled singular integral/integrodifferential equations is discretized using moment-method-oriented direct singular integral equation methods. Treating all singular integrals analytically via rapidly converging algorithms leads to numerically stable and efficient analytical expressions for all matrix elements. As a result, no numerical integration is required to compute these elements. Several numerical examples are presented to validate the algorithm and illustrate its convergence characteristics. Results are also presented that reveal the possibility of controlling the absorption efficiency by suitably selecting several geometrical and physical parameters of the structure.     

$$\nu $$ acceleration of statistical iterative methods for image restoration

Image restoration problem is an important topic which appears in many different scientific areas. Several solving techniques are available, but generally in real applications, from which large-scale linear systems arise, the choice falls on iterative algorithms. In particular statistical methods (Lucy–Richardson method, image space reconstruction algorithm) have been extensively studied in the literature. Since they have low convergence rates, it is necessary to employ acceleration strategies. At this time, the most popular is the one introduced in 1997 by Biggs and Andrews, called automatic acceleration by the authors. In the present paper we describe \(\nu \) acceleration, that is the translation of the idea behind \(\nu \)-method, conceived for speeding up Landweber method, in the context of statistical methods. Computational results, which compare accelerated and classical methods, show the effectiveness of this strategy, which is able to get better performance than automatic acceleration.     

A fast search algorithm for vector quantization usingL2-norm pyramid of codewords

Vector quantization for image compression requires expensive encoding time to find the closest codeword to the input vector. This paper presents a fast algorithm to speed up the closest codeword search process in vector quantization encoding. By using an appropriate topological structure of the codebook, we first derive a condition to eliminate unnecessary matching operations from the search procedure. Then, based on this elimination condition, a fast search algorithm is suggested. Simulation results show that with little preprocessing and memory cost, the proposed search algorithm significantly reduces the encoding complexity while maintaining the same encoding quality as that of the full search algorithm. It is also found that the proposed algorithm outperforms the existing search algorithms.     

基于子空间方法的最小二乘常模算法的研究

本文提出了两种基于子空间方法的常模算法,称为SUB_LSCMA和LSCMA_PASTd。SUB_LSCMA先采用奇异值分解(SVD)获得紧缩近似投影子空间(PASTd)算法的初值,用PASTd算法来计算信号子空间,并对该信号子空间作施密特正交化,将最小二乘常模算法(LSCMA)的权系数投影到正交的信号子空间上,目的是减轻噪声子空间干扰的影响,但复杂度比已有的基于直接对接收信号自相关矩阵做特征值分解(ED)的LSCM_SUB算法[6]复杂度低。LSCMA_PASTd在SUB_LSCMA的基础上作了进一步改进,采用改进的PASTd算法来计算信号子空间,该信号子空间具有正交性,并且对初值的选取不敏感,能运用于实际的多径衰落信道中。仿真结果表明这两种算法的收敛速度、跟踪性能和误码性能和LSCM_SUB算法基本相同,但是复杂度比LSCM_SUB算法低。     

Efficient singular element for finite element analysis of quasi-TEMtransmission lines and waveguides with sharp metal edges

The FEM presents a slow rate of convergence when it is used in the analysis of quasi-TEM transmission lines or homogeneous waveguides with field singularities. In order to improve this drawback, mesh techniques or vector elements that cope with the singularities can be used. A different solution is to employ scalar singular elements although, most of those that have been used are only compatible with first-order ordinary elements or can only be used with field singularities of order O(r^-1/2) and O(r^-1/3). In this paper, we present an improvement on the rate of convergence of FEM by employing a scalar singular element, which can be utilized for any order of singularity, is compatible with quadratic or higher order standard elements and is also easy to implement in standard finite element codes. Several transmission lines and waveguides with sharp metal edges have been analysed with a reduced number of degrees of freedom that compares well with other FEM approaches. We also show that electromagnetic fields computed using the proposed singular element have very good agreement with the ones theoretically expected from the singular edge condition     

Stochastic power control for cellular radio systems

For wireless communication systems, iterative power control algorithms have been proposed to minimize the transmitter power while maintaining reliable communication between mobiles and base stations. To derive deterministic convergence results, these algorithms require perfect measurements of one or more of the following parameters: (1) the mobile's signal-to-interference ratio (SIR) at the receiver; (2) the interference experienced by the mobile; and (3) the bit-error rate. However, these quantities are often difficult to measure and deterministic convergence results neglect the effect of stochastic measurements. We develop distributed iterative power control algorithms that use readily available measurements. Two classes of power control algorithms are proposed. Since the measurements are random, the proposed algorithms evolve stochastically and we define the convergence in terms of the mean-squared error (MSE) of the power vector from the optimal power vector that is the solution of a feasible deterministic power control problem. For the first class of power control algorithms using fixed step size sequences, we obtain finite lower and upper bounds for the MSE by appropriate selection of the step size. We also show that these bounds go to zero, implying convergence in the MSE sense, as the step size goes to zero. For the second class of power control algorithms, which are based on the stochastic approximations method and use time-varying step size sequences, we prove that the MSE goes to zero. Both classes of algorithms are distributed in the sense that each user needs only to know its own channel gain to its assigned base station and its own matched filter output at its assigned base station to update its power