Linearly Constrained Matrix Least Squares Problems: Theory And Algorithms

In the recent decades, with the development of society and the progress of science, more and more new problems which are urgent to be solved arise from the engineer technology and many other domains. Many of these problems can be reduced to linear systems of matrix equations and/or least squares problems with linear constraints on solutions, Those systems include Sylvester equation, Lyapunov equation, inverse eigenvalue problem and the corresponding least squares problems which have been widely considered in many applied domain. More and more people have been attracted in this research field.Theoretically, a least squares problem in matrix form can be rewritten in vector form by Kronecker product. So solutions of the matrix least squares problem are known in terms of higher dimensional column-vectors. So does it for matrix equations since a linear system of matrix equations can be looked as a least squares problem with zero residual. However, this equivalent transformation from matrix LS to vector LS may enlarge the coefficient matrices of the linear systems unnecessarily, which results in a great computation cost and storage requirement. Moreover, possible special structure of the coefficient matrices in the matrix system will be lost in the vector-expressions of general solutions, even if matrix solutions are reconstructed from the vector-expressions. To avoid these difficulties, basically to avoid introducing Kronecker products in the structure analysis of solutions or formulating solutions, matrix-level discussion or analysis for solutions of matrix LS problems is much interesting and there have been some valuable efforts on this issue. The techniques commonly used are some matrix-factorizations such as the generalized singular value decomposition (GSVD), the canonical correlation decomposition (CCD), and the quotient singular value decomposition (QSVD). In general, these factorizations are used to reduce matrix equations to be simple diagonal-like form so that the new systems can be easily solved by suitably partitioning the new matrix-variables - some sub-matrices are determined immediately and others are obtained by solving a small linear system. In the meantime, iterative methods for numerically solving the least squares problems are also considered. Some problems with special constraints have been solved. In general, the produce factorization applied on matrix LS problems requires proficient skill, depending on the system of matrix equations and the constraints on solutions. It is difficult to directly apply a consistent factorization produce on those related but different problems. Furthermore, those approaches are generally not robust. Minor modifications on the constraint may give rise to great change on solutions. A natural question kept in our mind is that whether we can find a uniform approach for analysis or iteratively solving the linear system of matrix equations with linear constrains on solutions. This thesis will concentrate on this question and try to give answers, based on a new viewpoint and jumping-off point of these well-known problems. We will present a frame work in both theory and algorithms. We believe that the methods proposed in this thesis is enlightening and helpful for other constrained matrix LS problems.The contributions of this thesis are outlined as follows:1. We character the linear constraint matrix-spaces by their lower-dimension parameter vector spaces, using matrix-form basis. Those properties will be used to analyze and solve the least squares problems with linear constraints, and for arbitrary matrix, we also present its orthogonal projection in the constrained space.2. We uncover the inherent relations between the solution-space of the matrix LS with (relatively stronger) constraints and the solution-space to the matrix LS with weaker constraints. Whether the former solution space is contained by the latter uniquely depends on the right-hand side matrix T of the equation. We prove that there exists an equivalent transformationφ(T) on the right-hand side matrix T such that the solution space of the constrained problem is not changed when the r.h.s, matrix T is replaced byφ(T). More importantly, the solution space of the weaker-constrained matrix LS with the transformed r.h.sφ(T) contains all the solutions of the original problem with the (stronger) constraints. Therefore, if the solution space associate to the weak-constraints and r.s.hφ(T) is known or can be easily obtained, the solution set of the strong-constrained problem can be easily constructed - it is the intersection of the strong-constraint space and the solution set of the weak-constraint problem. We discover this latent properties by Theorem 3.5. This transformation can be (not unique) the orthogonal projection of the r.h.s matrix on to the range space of the linear system of matrix equations corresponding to the strong-constraints. We present the details of constructing the equivalent map. This development is important for solving linearly constrained matrix LS problems since the matrix LS with weaker constraints (or without constraints) may have been solved. We apply this technique on some constrained matrix LS problems and obtain simple matrix-representations of solutions. Indeed, this technique can be used to handle the matrix LS problems when more linear constraints are added.3. We discuss two kinds of structure-matrix equations with specific constraints. Theoretically, a matrix eigenvalue decomposition are used to remove the constraints in our discussion. However, the eigenvalue decomposition is also gotten off later. General solutions of the constrained equations are reconstructed. Note that the formula of the general solutions is simple and eigenvector-free.4. We propose some matrix-form Krylov subspace methods for solving linearly con strained matrix LS problems. Basically, they are the algorithms CGLS, GMRES, bidiagonalization Lanczos, and LSQR in matrix-iteration. The matrix-form Krylov subspace methods are not trivial resetting of the vector-Krylov methods. The matrix-Krylov methods are derived by theoretically removing the constraints (using basis of the constraint space), employing Kronecker product to form a linear system in long-vector form, and applying vector-form Krylov methods. However, Kronecker products are not involved in the resulting matrix-form Krylov methods. We propose Theorem 5.2 to accomplish this vector-matrix iterative form transformation. Numerical experiments are reported to show the numerical efficiency of the matrix Krylov methods. We believe that the basic ideas proposed can be generalized to find other matrix-form iterative algorithms as well.