Simplified neural networks for solving linear least squares andtotal least squares problems in real time

In this paper a new class of simplified low-cost analog artificial neural networks with on chip adaptive learning algorithms are proposed for solving linear systems of algebraic equations in real time. The proposed learning algorithms for linear least squares (LS), total least squares (TLS) and data least squares (DLS) problems can be considered as modifications and extensions of well known algorithms: the row-action projection-Kaczmarz algorithm and/or the LMS (Adaline) Widrow-Hoff algorithms. The algorithms can be applied to any problem which can be formulated as a linear regression problem. The correctness and high performance of the proposed neural networks are illustrated by extensive computer simulation results.     

Partial condition number for the equality constrained linear least squares problem

In this paper, the normwise condition number of a linear function of the equality constrained linear least squares solution called the partial condition number is considered. Its expression and closed formulae are first presented when the data space and the solution space are measured by the weighted Frobenius norm and the Euclidean norm, respectively. Then, we investigate the corresponding structured partial condition number when the problem is structured. To estimate these condition numbers with high reliability, the probabilistic spectral norm estimator and the small-sample statistical condition estimation method are applied and two algorithms are devised. The obtained results are illustrated by numerical examples.     

Solving the least squares problem using a parallel linear algebra library

One of the important issues in the construction of a parallel Linear Algebra library is the choice of the process structure. The structure that is presented in this article allows for simple functional specifications of the processes and for their compositionality. Each functional specification describes the meaning of the parallel composition of a number of instances of a single process. The communication behaviours of the instances of a process do not occur in its specification. In such a specification, matrices and vectors occur as ordinary mathematical variables. The representations of the matrices and vectors are distributed across the process instances. All library processes conform to the same communication conventions. The library processes can be composed sequentially, without requiring global synchronisation between process calls. As an example, the parallel solution of the least squares problem is discussed.     

Solving the linear least squares problem with very high relative accuracy

A version of binary cascades iterative refinement (LSBCIR) for solving linear least squares problem min _x ‖b-Ax‖₂,A(m*n),m>n=rank(A), to a prescribed accuracy ε>0 is proposed and investigated. The time cost of the process in the sequential computation is of order $$mn^2 M(t_0 ) + mnM\left( {\left\lceil {\log _2 /\varepsilon } \right\rceil } \right)$$ , wheret ₀ is a basic mantissa length andM(t)=Kt ² is the time cost of two numbers multiplication infl(t).     

A unifying theorem for linear and total linear least squares

It is shown how both linear least-squares and total linear least-squares estimation schemes are special cases of a rank one modification of the data matrix or the sample covariance matrix. For a problem with n unknowns, there exist n linear least-squares solutions while the total linear least-squares solution is (generically) unique. When the signal-to-noise ratio is sufficiently high, the total least-squares solution is a nonnegative combination of the least-squares solutions     

Solving linear differential equations as a minimum norm least squares problem with error-bounds

Linear ordinary/partial differential equations (DEs) with linear boundary conditions (BCs) are posed as an error minimization problem. This problem has a linear objective function and a system of linear algebraic (constraint) equations and inequalities derived using both the forward and the backward Taylor series expansion. The DEs along with the BCs are approximated as linear equations/inequalities in terms of the dependent variables and their derivatives so that the total error due to discretization and truncation is minimized. The total error along with the rounding errors render the equations and inequalities inconsistent to an extent or, equivalently, near-consistent, in general. The degree of consistency will be reasonably high provided the errors are not dominant. When this happens and when the equations/inequalities are compatible with the DEs, the minimum value of the total discretization and truncation errors is taken as zero. This is because of the fact that these errors could be negative as well as positive with equal probability due to the use of both the backward and forward series. The inequalities are written as equations since the minimum value of the error (implying error-bound and written/expressed in terms of a nonnegative quantity) in each equation will be zero. The minimum norm least-squares solution (that always exists) of the resulting over-determined system will provide the required solution whenever the system has a reasonably high degree of consistency. A lower error-bound and an upper error-bound of the solution are also included to logically justify the quality/validity of the solution.     

Hierarchical least squares identification methods for multivariable systems

For multivariable discrete-time systems described by transfer matrices, we develop a hierarchical least squares iterative (HLSI) algorithm and a hierarchical least squares (HLS) algorithm based on a hierarchical identification principle. We show that the parameter estimation error given by the HLSI algorithm converges to zero for the deterministic cases, and that the parameter estimates by the HLS algorithm consistently converge to the true parameters for the stochastic cases. The algorithms proposed have significant computational advantage over existing identification algorithms. Finally, we test the proposed algorithms on an example and show their effectiveness.     

Accuracy of preconditioned CG-type methods for least squares problems

The conjugate gradient method with IMGS, an incomplete modified version of Gram-Schmidt orthogonalization to obtain an incomplete orthogonal factorization preconditioner, applied to the normal equations (PCGLS) is often used as the basic iterative method to solve the linear least squares problems. In this paper, a detailed analysis is given for understanding the effect of rounding errors on IMGS and determining the accuracy of computed solutions of PCGLS with IMGS for linear least squares problems in finite precision. It is shown that for a consistent system, the difference between the true residuals and the updated approximate residual vectors generated depends on the machine precision ε, on the maximum growth in norm of the iterates over their initial values, the norm of the true solution, and the condition number of R which is affected by the drop set in incomplete Gram-Schmidt factorization. Similar results are obtained for the difference between the true and computed solution for inconsistent systems. Numerical tests are carried out to confirm the theoretical conclusions.     

Hermitian tridiagonal solution with the least norm to quaternionic least squares problem

Quaternionic least squares (QLS) is an efficient method for solving approximate problems in quaternionic quantum theory. In view of the extensive applications of Hermitian tridiagonal matrices in physics, in this paper we list some properties of basis matrices and subvectors related to tridiagonal matrices, and give an iterative algorithm for finding Hermitian tridiagonal solution with the least norm to the quaternionic least squares problem by making the best use of structure of real representation matrices, we also propose a preconditioning strategy for the Algorithm LSQR-Q in Wang, Wei and Feng (2008) [14] and our algorithm. Numerical experiments are provided to verify the effectiveness of our method.     

Weighted least squares stationary approximations to linear systems

The problem of replacing the time-varying linear systemdot{X} = A(t)Xby a stationary onedot{Y} = BYis investigated. The matrixBis selected so thatX(t) = Y(t)in the interval [0, T]. Several quadratic criteria are proposed to aid in determining suitable candidate systems. One criterion for choosingBis initial condition dependent, and another bounds the "worst case" homogeneous system performance. Both of these criteria produce weighted least squares fits toA(t).     

Algorithm Q-LSQR for the least squares problem in quaternionic quantum theory

In this paper, an iterative algorithm for the standard quaternionic least squares problem is proposed without using the real (complex) representation. Our algorithm is implemented in the quaternion field and by means of direct quaternion arithmetic and is a natural generalization of the LSQR algorithm for the real least squares problem.     

Algebraic algorithms for least squares problem in quaternionic quantum theory

Quaternionic least squares (QLS) problem is one method of solving overdetermined sets of quaternion linear equations AX≈B that is appropriate when there is error in the matrix B. In this paper, by means of complex representation of a quaternion matrix, we introduce a concept of norm of quaternion matrices, discuss singular values and generalized inverses of a quaternion matrix, study the QLS problem and derive two algebraic methods for finding solutions of the QLS problem in quaternionic quantum theory.     

Block SOR methods for the solution of indefinite least squares problems

This paper describes a technique for constructing block SOR methods for the solution of the large and sparse indefinite least squares problem which involves minimizing a certain type of indefinite quadratic form. Two block SOR-based algorithms and convergence results are presented. The optimum parameters for the methods are also given. It has been shown both theoretically and numerically that the optimum block SOR methods have a faster convergence than block Jacobi and Gauss–Seidel methods.     

A Newton-like method for solving rank constrained linear matrix inequalities

This paper presents a Newton-like algorithm for solving systems of rank constrained linear matrix inequalities. Though local quadratic convergence of the algorithm is not a priori guaranteed or observed in all cases, numerical experiments, including application to an output feedback stabilization problem, show the effectiveness of the algorithm.     

SMO-based pruning methods for sparse least squares support vector machines

Solutions of least squares support vector machines (LS-SVMs) are typically nonsparse. The sparseness is imposed by subsequently omitting data that introduce the smallest training errors and retraining the remaining data. Iterative retraining requires more intensive computations than training a single nonsparse LS-SVM. In this paper, we propose a new pruning algorithm for sparse LS-SVMs: the sequential minimal optimization (SMO) method is introduced into pruning process; in addition, instead of determining the pruning points by errors, we omit the data points that will introduce minimum changes to a dual objective function. This new criterion is computationally efficient. The effectiveness of the proposed method in terms of computational cost and classification accuracy is demonstrated by numerical experiments.     

Saddle point least squares preconditioning of mixed methods

We present a simple way to discretize and precondition mixed variational formulations. Our theory connects with, and takes advantage of, the classical theory of symmetric saddle point problems and the theory of preconditioning symmetric positive definite operators. Efficient iterative processes for solving the discrete mixed formulations are proposed and choices for discrete spaces that are always compatible are provided. For the proposed discrete spaces and solvers, a basis is needed only for the test spaces and assembly of a global saddle point system is avoided. We prove sharp approximation properties for the discretization and iteration errors and also provide a sharp estimate for the convergence rate of the proposed algorithm in terms of the condition number of the elliptic preconditioner and the discrete $inf?sup$ and $sup?sup$ constants of the pair of discrete spaces.