Bounds on smooth solutions of underdetermined linear models for gas exchange

In recent literature, grossly underdetermined linear models have been developed for certain experimental techniques in respiratory physiology. Because physiologically sensible solutions of the models are reasonably assumed to be smooth, it is possible to recover such solutions using smoothed least-squares techniques. Bounds on the variability of smooth solutions satisfying the model can be generated using linear programming.The second author was supported in this work by New Zealand Medical Research Council Grant No. 81/65 to Dr. E. A. Harris, Greenlane Hospital, Auckland, New Zealand. The authors are indebted to Dr. Harris for his support and guidance in the physiological aspects of the work.     

Ill-Conditionedness Need not be Componentwise Near to Ill-Posedness for Least Squares Problems

The condition number of a problem measures the sensitivity of the answer to small changes in the input, where small refers to some distance measure. A problem is called ill-conditioned if the condition number is large, and it is called ill-posed if the condition number is infinity. It is known that for many problems the (normwise) distance to the nearest ill-posed problem is proportional to the reciprocal of the condition number. Recently it has been shown that for linear systems and matrix inversion this is also true for componentwise distances. In this note we show that this is no longer true for least squares problems and other problems involving rectangular matrices. Problems are identified which are arbitrarily ill-conditioned (in a componentwise sense) whereas any componentwise relative perturbation less than 1 cannot produce an ill-posed problem. Bounds are given using additional information on the matrix.     

A meshless method for the Cauchy problem in linear elastodynamics

In this paper, we establish new density result for the Navier equation. Based on the denseness of the elastic single-layer potential functions, the Cauchy problem for the Navier equation is investigated. The ill-posedness of this problem is given via the compactness of the operator defined by the potential function. The method combines the Newton’s method and minimum norm solution with discrepancy principle to solve an inverse problem. Convergence and stability estimates are then given with some examples for numerical verification on the efficiency of the proposed method.     

Low Rank Approximation of a Hankel Matrix by Structured Total Least Norm

The structure preserving rank reduction problem arises in many important applications. The singular value decomposition (SVD), while giving the closest low rank approximation to a given matrix in matrix L ₂ norm and Frobenius norm, may not be appropriate for these applications since it does not preserve the given structure. We present a new method for structure preserving low rank approximation of a matrix, which is based on Structured Total Least Norm (STLN). The STLN is an efficient method for obtaining an approximate solution to an overdetermined linear system AX B, preserving the given linear structure in the perturbation [E F] such that (A + E)X = B + F. The approximate solution can be obtained to minimize the perturbation [E F] in the L _p norm, where p = 1, 2, or . An algorithm is described for Hankel structure preserving low rank approximation using STLN with L _p norm. Computational results are presented, which show performances of the STLN based method for L ₁ and L ₂ norms for reduced rank approximation for Hankel matrices.     

Norm estimations for perturbations of the weighted Moore-Penrose inverse

For a complex matrix $A\in \mathbb{C}^{m\times n}$, the relationship between the weighted Moore-Penrose inverse $A^\dag_{M_1N_1}$ and $A^\dag_{M_2N_2}$ is studied, and an important formula is derived,where $M_1\in \mathbb{C}^{m\times m}, N_1\in\mathbb{C}^{n\times n}$ and $M_2\in \mathbb{C}^{m\times m}, N_2\in\mathbb{C}^{n\times n}$ are different pair of positive definite hermitian matrices. Based on this formula, this paper initiates the study of the perturbation estimations for $A^\dag_{MN}$ in the case that $A$ is fixed, whereas both $M$ and $N$ are variable. The obtained norm upper bounds are then applied to the perturbation estimations for the solutions to the weighted linear least squares problems.     

Developing the CGLS algorithm for the least squares solutions of the general coupled matrix equations

In the present paper, we consider the minimum norm solutions of the general least squares problem By developing the conjugate gradient least square (CGLS) method, we construct an efficient iterative method to solve this problem. The constructed iterative method can compute the solution group of the problem within a finite number of iterations in the absence of roundoff errors. Also it is shown that the method is stable and robust. Finally, by some numerical experiments, we demonstrate that the iterative method is effective and efficient. Copyright © 2013 John Wiley & Sons, Ltd.     

A RECURSIVE ALGORITHM AND ITS CONVERGENCE FOR PARAMETER ESTIMATION OF CONVOLUTION MODEL

In this article, the problem on the estimation of the convolution model parameters is considered. The recursive algorithm for estimating model parameters is introduced from the orthogonal procedure of the data, the convergence of this algorithm is theoretically discussed, and a sufficient condition for the convergence criterion of the orthogonal procedure is given. According to this condition, the recursive algorithm is convergent to model wavelet A- = （1, α1,..., αq）.     

Global analysis of continuous analogues of the Levenberg-Marquardt and Newton-Raphson methods for solving nonlinear equations

Summary Global analyses are given to continuous analogues of the Levenberg-Marquardt methoddx/dt=−(J ^t(x)J(x)+δI)⁻¹J^t(x)g(x), and the Newton-Raphson-Ben-Israel methoddx/dt=−J ⁺(x)g(x), for solving an over- and under-determined systemg(x)=0 of nonlinear equations. The characteristics of both methods are compared. Erros in some literature which dealt with related continous analogue methods are pointed out. The Institute of Statistical Mathematics     

基于模拟退火算法的最小一乘回归新算法

最小一乘准则由于其稳健性较好而在工程中得到广泛的应用,但求解最小一乘回归模型系数的算法往往过于复杂或只能用于样本和变量个数较少的情形.本文根据最小一乘的性质,把最小一乘问题变为组合优化问题,将模拟退火算法用在最小一乘模型的求解上,在后面的数值实验中取得了较好的效果。     

基于门限接受算法的正交最小一乘回归新算法

正交最小一乘方法由于其稳健性而在工程中有广泛的应用,然而求解线性模型正交最小一乘参数估计算法往往过于复杂或者只对样本和变量个数较少的问题适用.把正交最小一乘参数估计问题转化为组合优化问题,再使用门限接受算法求解,通过计算机仿真说明了本文算法的正确性和有效性.     

Condition numbers and perturbation analysis for the Tikhonov regularization of discrete ill‐posed problems

One of the most successful methods for solving the least‐squares problem min_x∥Ax?b∥₂ with a highly ill‐conditioned or rank deficient coefficient matrix A is the method of Tikhonov regularization. In this paper, we derive the normwise, mixed and componentwise condition numbers and componentwise perturbation bounds for the Tikhonov regularization. Our results are sharper than the known results. Some numerical examples are given to illustrate our results. Copyright © 2010 John Wiley & Sons, Ltd.     

A Class of Incomplete Orthogonal Factorization Methods. I: Methods and Theories

We present a class of incomplete orthogonal factorization methods based on Givens rotations for large sparse unsymmetric matrices. These methods include: Incomplete Givens Orthogonalization (IGO-method) and its generalisation (GIGO-method), which drop entries from the incomplete orthogonal and upper triangular factors by position; Threshold Incomplete Givens Orthogonalization (TIGO()-method), which drops entries dynamically by their magnitudes; and its generalisation (GTIGO(,p)-method), which drops entries dynamically by both their magnitudes and positions. Theoretical analyses show that these methods can produce a nonsingular sparse incomplete upper triangular factor and either a complete orthogonal factor or a sparse nonsingular incomplete orthogonal factor for a general nonsingular matrix. Therefore, these methods can potentially generate efficient preconditioners for Krylov subspace methods for solving large sparse systems of linear equations. Moreover, the upper triangular factor is an incomplete Cholesky factorization preconditioner for the normal equations matrix from least-squares problems.     

A method for the automatic selection and tuning of the parameters of a sparse SLE solver

A technique for the automatic selection of the method for solution of a sparse system of linear algebraic equations (SLE) and selection of the method parameters from the analysis of the SLE matrix of coefficients is presented. The parameters are selected so as to maximize the performance metric. A formal model of the performance of a SLE solver is presented and is used to formulate an algorithm for construction, precedent learning, and application of the proposed method. The method is approved for iterative SLE solvers from the PETSc parallel library of the MVS-100K supercomputer platform at the Interdepartmental Supercomputer Center of the Russian Academy of Sciences.     

A Variant of the ORTHOMIN(2) Method for Singular Linear Systems

For singular linear systems A x=b, ORTHOMIN(2) is known theoretically to attain the minimum residual min _xR nb–A x₂ under a certain condition. However, in the actual computation with finite precision arithmetic, the residual is often observed to be reduced further than the theoretically expected level. Therefore, we propose a variant of ORTHOMIN(2), which is mathematically equivalent to the original ORTHOMIN(2) method, but uses recurrence formulas that are different from those of ORTHOMIN(2); they contain alternative expressions for the auxiliary vector and the recurrence coefficients. Although our implementation has the same computational costs as ORTHOMIN(2), numerical experiments on singular systems show that our implementation is more accurate and less affected by rounding errors than ORTHOMIN(2).     

A note on optimality conditions for the Euclidean. Multifacility location problem

Thekey problem of the Euclidean multifacility location (EMFL) problem is to decide whether a givendead point is optimal. If it is not optimal, we wish to compute a descent direction. This paper extends the optimality conditions of Calamai and Conn and Overton to the case when the rows of the active constraints matrix are linearly dependent. We show that linear dependence occurs wheneverG, the graph of the coinciding facilities, has a cycle. In this case the key problem is formulated as a linear least squares problem with bounds on the Euclidean norms of certain subvectors.     

Inner and outer bounds for the solution set of parametric linear systems

Consider linear systems involving affine-linear dependencies on interval parameters. Presented is a free C-XSC software implementing a generalized parametric fixed-point iteration method for verified enclosure of the parametric solution set. Some specific features of the corresponding algorithm concerning sharp enclosure of the contracting matrix and inner approximation of the solution enclosure are discussed.     

二级价格控制问题满意解的基于LP与NLP过程的算法

基于 SAS/ OR优化软件求解线性规划的 LP过程与求解非线性规划的 NLP过程的强功能 ,本文提出求二级价格控制问题满意解的直接搜索法 ,给出用直接搜索法与边界搜索法相结合的用 LP与 NLP过程求二级价格控制问题的满意解的算法 ,通过实例给出重要步骤的 SAS程序 .并指出有待进一步研究的问题 .     

Latent scale linear models for multivariate ordinal responses and analysis by the method of weighted least squares

Summary A multivariate latent scale linear model is defined for multivariate ordered categorical responses and inference procedures based on the weighted least squares method are developed. Several applications of the model are suggested and illustrated through an analysis of real data. Asymptotic properties of the weighted least squares method are examined and some consequences of misspecification of the model are also discussed.     

A modified candecomp algorithm for fitting the latent class model: Implementation and evaluation

In this paper an implementation is discussed of a modified CANDECOMP algorithm for fitting Lazarsfeld's latent class model. The CANDECOMP algorithm is modified such that the resulting parameter estimates are non-negative and ‘best asymptotically normal’. In order to achieve this, the modified CANDECOMP algorithm minimizes a weighted least squares function instead of an unweighted least squares function as the traditional CANDECOMP algorithm does. To evaluate the new procedure, the modified CANDECOMP procedure with different weighting schemes is compared on five published data sets with the widely-used iterative proportional fitting procedure for obtaining maximum likelihood estimates of the parameters in the latent class model. It is found that, with appropriate weights, the modified CANDECOMP algorithm yields solutions that are nearly identical with those obtained by means of the maximum likelihood procedure. While the modified CANDECOMP algorithm tends to be computationally more intensive than the maximum likelihood method, it is very flexible in that it easily allows one to try out different weighting schemes.     

A fast and accurate algorithm for solving linear systems associated with a class of negative matrix

A class of negative matrices including Vandermonde-like matrices tends to be extremely ill-conditioned, and linear systems associated with this class of matrices appear in the polynomial interpolation problems. In this article, we present a fast and accurate algorithm with $O(n^2)$ complexity to solve the linear systems whose coefficient matrices belong to the class of negative matrix. We show that the inverse of any such matrix is generated in a subtraction-free manner. Consequently, the solutions of linear systems associated with the class of negative matrix are accurately determined by parameterization matrices of coefficient matrices, and a pleasantly componentwise forward error is provided to illustrate that each component of the solution is computed to high accuracy. Numerical experiments are performed to confirm the claimed high accuracy.