Fast Parallel QR Decomposition of Block-Toeplitz Matrices

A fast algorithm FBTQ is presented which computes the QR factorization a block-Toeplitz matrix A (A∈R) in O(mns3) multiplications. We prove that the QR decomposition of A and the inverse Cholesky decomposition can be computed in parallel using the sametransformation.We also prove that some kind of Toeplltz-block matrices can he transformed into the corresponding block-Toeplitz matrices.

Effective Methods of QR-Decompositions of Square Complex Matrices by Fast Discrete Signal-Induced Heap Transforms

The purpose of this work is to present an effective tool for computing different QR-decompositions of a complex nonsingular square matrix. The concept of the discrete signal-induced heap transform (DsiHT, Grigoryan 2006) is used. This transform is fast, has a unique algorithm for any length of the input vector/signal and can be used with different complex basic 2 × 2 transforms. The DsiHT is zeroing all components of the input signal while moving or heaping the energy of the signal to one component, for instance the first one. We describe three different types of QR-decompositions that use the basic transforms with the T, G, and M-type complex matrices we introduce, as well as without matrices but using analytical formulas. We also present the mixed QR-decomposition, when different type DsiHTs are used in different stages of the algorithm. The number of such decompositions is greater than 3(N-1), for an N × N complex matrix. Examples of the QR-decomposition are described in detail for the 4 × 4 and 6 × 6 complex matrices and compared with the known method of Householder transforms. The precision of the QR-decompositions of N × N matrices, when N are 6, 13, 17, 19, 21, 40, 64, 100, 128, 201, 256, and 400 is also compared. The MATLAB-based scripts of the codes for QR-decompositions by the described DsiHTs are given.

A TSE based design for MMSE and QRD of MIMO systems based on ASIP

A Taylor series expansion(TSE) based design for minimum mean-square error(MMSE) and QR decomposition(QRD) of multi-input and multi-output(MIMO) systems is proposed based on application specific instruction set processor(ASIP), which uses TSE algorithm instead of resource-consuming reciprocal and reciprocal square root(RSR) operations.The aim is to give a high performance implementation for MMSE and QRD in one programmable platform simultaneously.Furthermore, instruction set architecture(ISA) and the allocation of data paths in single instruction multiple data-very long instruction word(SIMD-VLIW) architecture are provided, offering more data parallelism and instruction parallelism for different dimension matrices and operation types.Meanwhile, multiple level numerical precision can be achieved with flexible table size and expansion order in TSE ISA.The ASIP has been implemented to a 28 nm CMOS process and frequency reaches 800 MHz.Experimental results show that the proposed design provides perfect numerical precision within the fixed bit-width of the ASIP, higher matrix processing rate better than the requirements of 5G system and more rate-area efficiency comparable with ASIC implementations.

Rice condition numbers of QR and Cholesky factorizations

A condition number is an amplification coefficient due to errors in computing. Thus the theory of condition numbers plays an important role in error analysis. In this paper, following the approach of Rice, condition numbers are defined for factors of some matrix factorizations such as the Cholesky factorization of a symmetric positive definite matrix and QR factorization of a general matrix. The condition numbers are derived by a technique of analytic expansion of the factor dependent on one parameter and matrix-vector equation. Condition numbers of the Cholesky and QR factors are different from the ones previously introduced by other authors, but similar to Chang's results. In Cholesky factorization, corresponding with the condition number of the factor matrix L , K _L is a low bound of Stewart's condition number K .

Orthogonal-triangular decomposition ghost imaging

Ghost imaging(GI)offers great potential with respect to conventional imaging techniques.However,there are still some obstacles for reconstructing images with high quality,especially in the case that the orthogonal measurement matrix is impossible to construct.In this paper,we propose a new scheme based on the orthogonal-triangular(QR)decomposition,named QR decomposition ghost imaging(QRGI)to reconstruct a better image with good quality.In the scheme,we can change the randomly non-orthogonal measurement matrix into orthonormal matrix by performing QR decomposition in two cases.(1)When the random measurement matrix is square,it can be firstly decomposed into an orthogonal matrix Q and an upper triangular matrix R.Then let the off-diagonal values of R equal to 0.0,the diagonal elements of R equal to a constant k,where k is the average of all values of the main diagonal,so the resulting measurement matrix can be obtained.(2)When the random measurement matrix is with full rank,we firstly compute its transpose,and followed with above QR operation.Finally,the image of the object can be reconstructed by correlating the new measurement matrix and corresponding bucket values.Both experimental and simulation results verify the feasibility of the proposed QRGI scheme.Moreover,the results also show that the proposed QRGI scheme could improve the imaging quality comparing to traditional GI(TGI)and differential GI(DGI).Besides,in comparison with the singular value decomposition ghost imaging(SVDGI),the imaging quality and the reconstruction time by using QRGI are similar to those by using SVDGI,while the computing time(the time consuming on the light patterns computation)is substantially shortened.

INVERSE QR ITERATIVE METHOD FOR SUBSPACE TRACKING

The Bi-LS method based on QR decomposition provides a convenient framework for de-veloping efficient subspace tracking algorithms.To overcome the shortcoming of the backsubstitution step and improve the parallel architecture of the Bi-LS algorithms,a Bi-LS subspace tracking algorithm based on Inverse QR(IQR) decomposition is developed.The proposed IQR iterative algorithm for subspace tracking is well suited for the parallel implementation in the systolic array.Simulation results are presented to illustrate the effectiveness of the proposed IQR subspace tracking algorithm.

Novel K-best detection algorithms for MIMO system

Aiming at the optimum path excluding characteristics and the full constellation searching characteristics of the K-best detection algorithm, an improved-performance K-best detection algorithm and several reduced-complexity K-best detection algorithms are proposed. The improved-performance K-best detection algorithm deploys minimum mean square error （MMSE） filtering of a channel matrix before QR decomposition. This algorithm can decrease the probability of excluding the optimum path and achieve better performance. The reducedcomplexity K-best detection algorithms utilize a sphere decoding method to reduce searching constellation points. Simulation results show that the improved performance K-best detection algorithm obtains a 1 dB performance gain compared to the K- best detection algorithm based on sorted QR decomposition （SQRD）. Performance loss occurs when K = 4 in reduced complexity K-best detection algorithms. When K = 8, the reduced complexity K-best detection algorithms require less computational effort compared with traditional K-best detection algorithms and achieve the same performance.

Generalized cubature quadrature Kalman filters:derivations and extensions

A new Gaussian approximation nonlinear filter called generalized cubature quadrature Kalman filter (GCQKF) is introduced for nonlinear dynamic systems. Based on standard GCQKF, two extensions are developed, namely square root generalized cubature quadrature Kalman filter (SR-GCQKF) and iterated generalized cubature quadrature Kalman filter (I-GCQKF). In SR-GCQKF, the QR decomposition is exploited to alter the Cholesky decomposition and both predicted and filtered error covariances have been propagated in square root format to make sure the numerical stability. In I-GCQKF, the measurement update step is executed iteratively to make full use of the latest measurement and a new terminal criterion is adopted to guarantee the increase of likelihood. Detailed numerical experiments demonstrate the superior performance on both tracking stability and estimation accuracy of I-GCQKF and SR-GCQKF compared with GCQKF.

KERNEL NEIGHBORHOOD PRESERVING EMBEDDING FOR CLASSIFICATION

The Neighborhood Preserving Embedding(NPE) algorithm is recently proposed as a new dimensionality reduction method.However, it is confined to linear transforms in the data space.For this, based on the NPE algorithm, a new nonlinear dimensionality reduction method is proposed, which can preserve the local structures of the data in the feature space.First, combined with the Mercer kernel, the solution to the weight matrix in the feature space is gotten and then the corresponding eigenvalue problem of the Kernel NPE(KNPE) method is deduced.Finally, the KNPE algorithm is resolved through a transformed optimization problem and QR decomposition.The experimental results on three real-world data sets show that the new method is better than NPE, Kernel PCA(KPCA) and Kernel LDA(KLDA) in performance.

A NEW LEAST SQUARE ALGORITHM FOR LINEAR PROGRAMMING

By attacking the linear programming problems from their dual side,a new general algorithm for linear programming is developed.At each iteration,the algorithm finds a feasible descent search direction by handling a least square problem associated with the dual system,using QR decomposition technique.The new method is a combination of pivot method and interior-point method.It in fact not only reduces the possibility of difficulty arising from degeneracy,but also has the same advantages as pivot method in warm-start to resolve linear programming problems.Numerical results of a group of randomly constructed problems are very encouraging.

INTERFERENCE MITIGATION FOR ASYNCHRONOUS COOPERATIVE STBC-OFDM SYSTEMS

This paper addresses the problem of interference mitigation in cooperative Space Time Block Coded Orthogonal Frequency Division Multiplexing (STBC-OFDM) systems in the presence of asyn-chronism. This scheme first preprocesses the received ST codewords to convert the equivalent fading matrix into a suboptimal ordering upper triangular form based on low complexity permutation QR decomposition, and then suppresses the InterCarrier Interference (ICI) and InterSymbol Interference (ISI) by exploiting Successive Interference Cancellation (SIC) technique. Simulation results show that the performance of the proposed algorithm slightly outmatches or asymptotically approaches to that of the existing Minimum Mean Square Error (MMSE) detector depending on the magnitude of the Carrier Frequency Offsets (CFOs) but with less complexity.

On Linear Algebra for Non Mathematics Majors

To find out what knowledge in linear algebra is essential to non-mathematics students, a reverse tracking method was used. Based on practical problems likely to encountered by students in subsequent engineering courses, the minimum contents required has been determined. Rules are proposed to meet the background of most freshman students. An application oriented, easy to understand, computer based text book “Applied Popular Linear Algebra with MATLAB” [1] was published.

The structured total least squares algorithm research for passive location based on angle information

Based on the constrained total least squares （CTLS） passive location algorithm with bearing-only measurements, in this paper, the same passive location problem is transformed into the structured total least squares （STLS） problem.The solution of the STLS problem for passive location can be obtained using the inverse iteration method.It also expatiates that both the STLS algorithm and the CTLS algorithm have the same location mean squares error under certain condition.Finally, the article presents a kind of location and tracking algorithm for moving target by combining STLS location algorithm with Kalman filter （KF）.The efficiency and superiority of the proposed algorithms can be confirmed by computer simulation results.

NONMONOTONIC REDUCED PROJECTED HESSIAN METHOD VIA AN AFFINE SCALING INTERIOR MODIFIED GRADIENT PATH FOR BOUNDED-CONSTRAINED OPTIMIZATION

The authors propose an affine scaling modified gradient path method in association with reduced projective Hessian and nonmonotonic interior backtracking line search techniques for solving the linear equality constrained optimization subject to bounds on variables. By employing the QR decomposition of the constraint matrix and the eigensystem decomposition of reduced projective Hes- sian matrix in the subproblem, the authors form affine scaling modified gradient curvilinear path very easily. By using interior backtracking line search technique, each iterate switches to trial step of strict interior feasibility. The global convergence and fast local superlinear/quadratical convergence rates of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.