A class of preconditioned iterative methods, i.e., preconditioned generalized accelerated overrelaxation (GAOR) methods, is proposed to solve linear systems based on a class of weighted linear least squares problems...A class of preconditioned iterative methods, i.e., preconditioned generalized accelerated overrelaxation (GAOR) methods, is proposed to solve linear systems based on a class of weighted linear least squares problems. The convergence and comparison results are obtained. The comparison results show that the convergence rate of the preconditioned iterative methods is better than that of the original methods. Furthermore, the effectiveness of the proposed methods is shown in the numerical experiment.展开更多
Linear Least Squares(LLS) problems are particularly difficult to solve because they are frequently ill-conditioned, and involve large quantities of data. Ill-conditioned LLS problems are commonly seen in mathematics...Linear Least Squares(LLS) problems are particularly difficult to solve because they are frequently ill-conditioned, and involve large quantities of data. Ill-conditioned LLS problems are commonly seen in mathematics and geosciences, where regularization algorithms are employed to seek optimal solutions. For many problems, even with the use of regularization algorithms it may be impossible to obtain an accurate solution. Riley and Golub suggested an iterative scheme for solving LLS problems. For the early iteration algorithm, it is difficult to improve the well-conditioned perturbed matrix and accelerate the convergence at the same time. Aiming at this problem, self-adaptive iteration algorithm(SAIA) is proposed in this paper for solving severe ill-conditioned LLS problems. The algorithm is different from other popular algorithms proposed in recent references. It avoids matrix inverse by using Cholesky decomposition, and tunes the perturbation parameter according to the rate of residual error decline in the iterative process. Example shows that the algorithm can greatly reduce iteration times, accelerate the convergence,and also greatly enhance the computation accuracy.展开更多
The matrix least squares (LS) problem minx ||AXB^T--T||F is trivial and its solution can be simply formulated in terms of the generalized inverse of A and B. Its generalized problem minx1,x2 ||A1X1B1^T + A2X2...The matrix least squares (LS) problem minx ||AXB^T--T||F is trivial and its solution can be simply formulated in terms of the generalized inverse of A and B. Its generalized problem minx1,x2 ||A1X1B1^T + A2X2B2^T - T||F can also be regarded as the constrained LS problem minx=diag(x1,x2) ||AXB^T -T||F with A = [A1, A2] and B = [B1, B2]. The authors transform T to T such that min x1,x2 ||A1X1B1^T+A2X2B2^T -T||F is equivalent to min x=diag(x1 ,x2) ||AXB^T - T||F whose solutions are included in the solution set of unconstrained problem minx ||AXB^T - T||F. So the general solutions of min x1,x2 ||A1X1B^T + A2X2B2^T -T||F are reconstructed by selecting the parameter matrix in that of minx ||AXB^T - T||F.展开更多
In this paper, we extend the alternate Broyden's method to the multiple version fbi solving lincar leastsquarc systems with multiple right-hand sides. We show that the method possesses property of a finite tcrmina...In this paper, we extend the alternate Broyden's method to the multiple version fbi solving lincar leastsquarc systems with multiple right-hand sides. We show that the method possesses property of a finite tcrmination.Some numerical cxperiments are gi von to inustrate the effectiveness of the method.展开更多
This paper gives a class of descent methods for nonlinear least squares solution. A class of updating formulae is obtained by using generalized inverse matrices. These formulae generate an approximation to the second ...This paper gives a class of descent methods for nonlinear least squares solution. A class of updating formulae is obtained by using generalized inverse matrices. These formulae generate an approximation to the second part of the Hessian matrix of the objective function, and are updated in such a way that the resulting approximation to the whole Hessian matrix is the convex class of Broyden-like up-dating formulae. It is proved that the proposed updating formulae are invariant under linear transformation and that the class of factorized quasi-Newton methods are locally and superlinearly convergent. Numerical results are presented and show that the proposed methods are promising.展开更多
A new column recurrence algorithm based on the classical Greville method and modified Huang update is proposed for computing generalized inverse matrix and least squares solution. The numerical results have shown the ...A new column recurrence algorithm based on the classical Greville method and modified Huang update is proposed for computing generalized inverse matrix and least squares solution. The numerical results have shown the high efficiency and stability of the algorithm.展开更多
Separable nonlinear least squares problems are a special class of nonlinear least squares problems, where the objective functions are linear and nonlinear on different parts of variables. Such problems have broad appl...Separable nonlinear least squares problems are a special class of nonlinear least squares problems, where the objective functions are linear and nonlinear on different parts of variables. Such problems have broad applications in practice. Most existing algorithms for this kind of problems are derived from the variable projection method proposed by Golub and Pereyra, which utilizes the separability under a separate framework. However, the methods based on variable projection strategy would be invalid if there exist some constraints to the variables, as the real problems always do, even if the constraint is simply the ball constraint. We present a new algorithm which is based on a special approximation to the Hessian by noticing the fact that certain terms of the Hessian can be derived from the gradient. Our method maintains all the advantages of variable projection based methods, and moreover it can be combined with trust region methods easily and can be applied to general constrained separable nonlinear problems. Convergence analysis of our method is presented and numerical results are also reported.展开更多
For the linear least squares problem with coefficient matrix columns being highly correlated, we develop a greedy randomized Gauss-Seidel method with oblique direction. Then the corresponding convergence result is ded...For the linear least squares problem with coefficient matrix columns being highly correlated, we develop a greedy randomized Gauss-Seidel method with oblique direction. Then the corresponding convergence result is deduced. Numerical examples demonstrate that our proposed method is superior to the greedy randomized Gauss-Seidel method and the randomized Gauss-Seidel method with oblique direction.展开更多
This paper gives an expression of exact solntion for one-dimension generalized least squars problems under a constraint condition.and discusses the scope of solutions.The calculating methods,iteration stabs and a conv...This paper gives an expression of exact solntion for one-dimension generalized least squars problems under a constraint condition.and discusses the scope of solutions.The calculating methods,iteration stabs and a convergence theorem are given for n-dimension linear generalized least squares problems.展开更多
Time-differences-of-arrival (TDOA) and gain-ratios-of- arrival (GROA) measurements are used to determine the passive source location. Based on the measurement models, the con- strained weighted least squares (CWL...Time-differences-of-arrival (TDOA) and gain-ratios-of- arrival (GROA) measurements are used to determine the passive source location. Based on the measurement models, the con- strained weighted least squares (CWLS) estimator is presented. Due to the nonconvex nature of the CWLS problem, it is difficult to obtain its globally optimal solution. However, according to the semidefinite relaxation, the CWLS problem can be relaxed as a convex semidefinite programming problem (SDP), which can be solved by using modern convex optimization algorithms. Moreover, this relaxation can be proved to be tight, i.e., the SDP solves the relaxed CWLS problem, and this hence guarantees the good per- formance of the proposed method. Furthermore, this method is extended to solve the localization problem with sensor position errors. Simulation results corroborate the theoretical results and the good performance of the proposed method.展开更多
Traditional methods for solving linear systems have quickly become imprac-tical due to an increase in the size of available data.Utilizing massive amounts of data is further complicated when the data is incomplete or ...Traditional methods for solving linear systems have quickly become imprac-tical due to an increase in the size of available data.Utilizing massive amounts of data is further complicated when the data is incomplete or has missing entries.In this work,we address the obstacles presented when working with large data and incom-plete data simultaneously.In particular,we propose to adapt the Stochastic Gradient Descent method to address missing data in linear systems.Our proposed algorithm,the Stochastic Gradient Descent for Missing Data method(mSGD),is introduced and theoretical convergence guarantees are provided.In addition,we include numerical experiments on simulated and real world data that demonstrate the usefulness of our method.展开更多
基金supported by the National Natural Science Foundation of China (No. 11071033)the Fundamental Research Funds for the Central Universities (No. 090405013)
文摘A class of preconditioned iterative methods, i.e., preconditioned generalized accelerated overrelaxation (GAOR) methods, is proposed to solve linear systems based on a class of weighted linear least squares problems. The convergence and comparison results are obtained. The comparison results show that the convergence rate of the preconditioned iterative methods is better than that of the original methods. Furthermore, the effectiveness of the proposed methods is shown in the numerical experiment.
基金supported by Open Fund of Engineering Laboratory of Spatial Information Technology of Highway Geological Disaster Early Warning in Hunan Province(Changsha University of Science&Technology,kfj150602)Hunan Province Science and Technology Program Funded Projects,China(2015NK3035)+1 种基金the Land and Resources Department Scientific Research Project of Hunan Province,China(2013-27)the Education Department Scientific Research Project of Hunan Province,China(13C1011)
文摘Linear Least Squares(LLS) problems are particularly difficult to solve because they are frequently ill-conditioned, and involve large quantities of data. Ill-conditioned LLS problems are commonly seen in mathematics and geosciences, where regularization algorithms are employed to seek optimal solutions. For many problems, even with the use of regularization algorithms it may be impossible to obtain an accurate solution. Riley and Golub suggested an iterative scheme for solving LLS problems. For the early iteration algorithm, it is difficult to improve the well-conditioned perturbed matrix and accelerate the convergence at the same time. Aiming at this problem, self-adaptive iteration algorithm(SAIA) is proposed in this paper for solving severe ill-conditioned LLS problems. The algorithm is different from other popular algorithms proposed in recent references. It avoids matrix inverse by using Cholesky decomposition, and tunes the perturbation parameter according to the rate of residual error decline in the iterative process. Example shows that the algorithm can greatly reduce iteration times, accelerate the convergence,and also greatly enhance the computation accuracy.
基金supported in part by the Social Science Foundation of Ministry of Education(07JJD790154)the National Science Foundation for Young Scholars (60803076)+2 种基金the Natural Science Foundation of Zhejiang Province (Y6090211)Foundation of Education Department of Zhejiang Province (20070590)the Young Talent Foundation of Zhejiang Gongshang University
文摘The matrix least squares (LS) problem minx ||AXB^T--T||F is trivial and its solution can be simply formulated in terms of the generalized inverse of A and B. Its generalized problem minx1,x2 ||A1X1B1^T + A2X2B2^T - T||F can also be regarded as the constrained LS problem minx=diag(x1,x2) ||AXB^T -T||F with A = [A1, A2] and B = [B1, B2]. The authors transform T to T such that min x1,x2 ||A1X1B1^T+A2X2B2^T -T||F is equivalent to min x=diag(x1 ,x2) ||AXB^T - T||F whose solutions are included in the solution set of unconstrained problem minx ||AXB^T - T||F. So the general solutions of min x1,x2 ||A1X1B^T + A2X2B2^T -T||F are reconstructed by selecting the parameter matrix in that of minx ||AXB^T - T||F.
文摘In this paper, we extend the alternate Broyden's method to the multiple version fbi solving lincar leastsquarc systems with multiple right-hand sides. We show that the method possesses property of a finite tcrmination.Some numerical cxperiments are gi von to inustrate the effectiveness of the method.
文摘This paper gives a class of descent methods for nonlinear least squares solution. A class of updating formulae is obtained by using generalized inverse matrices. These formulae generate an approximation to the second part of the Hessian matrix of the objective function, and are updated in such a way that the resulting approximation to the whole Hessian matrix is the convex class of Broyden-like up-dating formulae. It is proved that the proposed updating formulae are invariant under linear transformation and that the class of factorized quasi-Newton methods are locally and superlinearly convergent. Numerical results are presented and show that the proposed methods are promising.
文摘A new column recurrence algorithm based on the classical Greville method and modified Huang update is proposed for computing generalized inverse matrix and least squares solution. The numerical results have shown the high efficiency and stability of the algorithm.
基金Chinese NSF grant 10231060the CAS Knowledge Innovation Program
文摘Separable nonlinear least squares problems are a special class of nonlinear least squares problems, where the objective functions are linear and nonlinear on different parts of variables. Such problems have broad applications in practice. Most existing algorithms for this kind of problems are derived from the variable projection method proposed by Golub and Pereyra, which utilizes the separability under a separate framework. However, the methods based on variable projection strategy would be invalid if there exist some constraints to the variables, as the real problems always do, even if the constraint is simply the ball constraint. We present a new algorithm which is based on a special approximation to the Hessian by noticing the fact that certain terms of the Hessian can be derived from the gradient. Our method maintains all the advantages of variable projection based methods, and moreover it can be combined with trust region methods easily and can be applied to general constrained separable nonlinear problems. Convergence analysis of our method is presented and numerical results are also reported.
文摘For the linear least squares problem with coefficient matrix columns being highly correlated, we develop a greedy randomized Gauss-Seidel method with oblique direction. Then the corresponding convergence result is deduced. Numerical examples demonstrate that our proposed method is superior to the greedy randomized Gauss-Seidel method and the randomized Gauss-Seidel method with oblique direction.
文摘This paper gives an expression of exact solntion for one-dimension generalized least squars problems under a constraint condition.and discusses the scope of solutions.The calculating methods,iteration stabs and a convergence theorem are given for n-dimension linear generalized least squares problems.
基金supported by the National Natural Science Foundation of China(61201282)the Science and Technology on Communication Information Security Control Laboratory Foundation(9140C130304120C13064)
文摘Time-differences-of-arrival (TDOA) and gain-ratios-of- arrival (GROA) measurements are used to determine the passive source location. Based on the measurement models, the con- strained weighted least squares (CWLS) estimator is presented. Due to the nonconvex nature of the CWLS problem, it is difficult to obtain its globally optimal solution. However, according to the semidefinite relaxation, the CWLS problem can be relaxed as a convex semidefinite programming problem (SDP), which can be solved by using modern convex optimization algorithms. Moreover, this relaxation can be proved to be tight, i.e., the SDP solves the relaxed CWLS problem, and this hence guarantees the good per- formance of the proposed method. Furthermore, this method is extended to solve the localization problem with sensor position errors. Simulation results corroborate the theoretical results and the good performance of the proposed method.
基金Needell was partially supported by NSF CAREER Grant No.1348721,NSF BIGDATA 1740325the Alfred P.Sloan Fellowship.Ma was supported in part by NSF CAREER Grant No.1348721,the CSRC Intellisis Fellowshipthe Edison Interna-tional Scholarship.
文摘Traditional methods for solving linear systems have quickly become imprac-tical due to an increase in the size of available data.Utilizing massive amounts of data is further complicated when the data is incomplete or has missing entries.In this work,we address the obstacles presented when working with large data and incom-plete data simultaneously.In particular,we propose to adapt the Stochastic Gradient Descent method to address missing data in linear systems.Our proposed algorithm,the Stochastic Gradient Descent for Missing Data method(mSGD),is introduced and theoretical convergence guarantees are provided.In addition,we include numerical experiments on simulated and real world data that demonstrate the usefulness of our method.