From: stewart@cs.umd.edu (G. W. Stewart)
Newsgroups: sci.math.stat
Subject: Re: Least Square Errors
Date: 10 Sep 92 00:09:07 GMT
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742

In article <1992Sep9.192431.13546@cbis.ece.drexel.edu> chaas@coe.drexel.edu (Chuck Haas) writes:
>What you propose to do is reasonable, and amounts to constrained least
>squares.  There is a fair body of literature on constrained least
>squares.  Your proposed method is also a degenerate case of a weighted
>least squares problem, in which not all dependent values are measured
>with the same lack of precision, and so that a poorer fit is tolerated at
>those more imprecisely measured points.

Chuck Haas is certainly right about there being a fair body of
literature on the subject of constrained least squares.  I am
appending a dump from my personal bibliography.  Since I am a
numerical analyst, it largely concerns computational methods and
perturbation theory.  There is more in the statistics journals.

Pete Stewart

\begin{thebibliography}{10}

\bibitem{barl:88}
J.~L. Barlow.
\newblock Error analysis and implementation aspects of deferred correction for
  equality constrained least squares problems.
\newblock {\em SIAM Journal on Numerical Analysis}, 25:1340--1358, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{baha:88}
J.~L. Barlow and S.~L. Handy.
\newblock The direct solution of weighted and equality constrained
  least-squares problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  9:704--716, 1988.

\bibitem{banp:88}
J.~L. Barlow, N.~K. Nichols, and R.~J. Plemmons.
\newblock Iterative methods for equality-constrained least squares problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  9:892--906, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{bjor:84}
{\AA}.~Bj{\"o}rck.
\newblock A general updating algorithm for constrained linear least squares
  problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  5:394--402., 1984.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{bjor:88b}
{\AA}.~Bj{\"o}rck.
\newblock A bidiagonalization algorithm for solving ill-posed system of linear
  equations.
\newblock {\em BIT}, 28:659--670, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{clos:88}
D.~I. Clark and M.~R. Osborne.
\newblock On linear restricted and interval least-squares problems.
\newblock {\em IMA Journal on Numerical Analysis}, 8:23--36, 1988.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{deap:78}
P.~Deuflhard and V.~Apostolescu.
\newblock An underrelaxed {Gauss-Newton} method for equality constrained
  nonlinear least squares.
\newblock In J.~Stoer, editor, {\em In Proceedings 8th IFIP Conference on
  Optimization Techniques}, volume~7, pages 22--32. Springer Verlag, 1978.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{eila:75}
E.~L. Eichhorn and C.~L. Lawson.
\newblock An {ALGOL} procedure for solution of constrained least squares
  problems.
\newblock Computing Memorandum No. 374, JPL, Pasadena, California, 1975.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{elde:77a}
L.~Eld{\`e}n.
\newblock {\em Numerical Analysis of Regularization and Constrained Least
  Square Methods}.
\newblock PhD thesis, Linkoping Studies in Science and Technology, Linkoping,
  Sweden, 1977.
\newblock Cited in \cite{govl:89}.

\bibitem{elde:80}
L.~Eld\'en.
\newblock Perturbation theory for the least squares problem with linear
  equality constraints.
\newblock {\em SIAM Journal on Numerical Analysis}, 17:338--350, 1980.

\bibitem{elde:83}
L.~Eld\'en.
\newblock A weighted pseudoinverse, generalized singular values, and
  constrained least squares problems.
\newblock {\em BIT}, 22:487--502, 1983.

\bibitem{flet:81}
R.~Fletcher.
\newblock {\em Practical Methods of Optimization, Vol. 2, Constrained
  Optimization}.
\newblock John Wiley, New York, 1981.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{gand:81}
W.~Gander.
\newblock Least squares with a quadratic constraint.
\newblock {\em Numerische Mathematik}, 36:291--307, 1981.

\bibitem{gay:84}
D.~M. Gay.
\newblock A trust-region approach to linearly constrained optimization.
\newblock In D.F. Griffiths, editor, {\em In Proceedings of the 1983 Dundee
  Conference on Numerical Analysis}, pages 72--105, New York, 1984. Springer
  Verlag.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{gimu:76}
P.E. Gill and W.~Murray.
\newblock Nonlinear least squares and nonlinearly constrained optimization.
\newblock In {\em In Proceedings Dundee Conference on Numerical Analysis 1975},
  New York, 1976. Springer Verlag.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{govl:89}
G.~H. Golub and C.~F. Van~Loan.
\newblock {\em Matrix Computations}.
\newblock Johns Hopkins University Press, Baltimore, Maryland, 2nd edition,
  1989.

\bibitem{govm:91}
G.~H. Golub and U.~von Matt.
\newblock Quadratically constrained least squares and quadratic problems.
\newblock {\em Numerische Mathematik}, 59:561--580, 1991.

\bibitem{hans:86}
R.~J. Hanson.
\newblock Linear least squares with bounds and linear constraints.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  7:826--834, 1986.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{haha:81}
K.~H. Haskell and R.~J. Hanson.
\newblock An algorithm for linear least squares problems with equality and
  nonnegativity constraints.
\newblock {\em Mathematical Programming}, 21:98--118, 1981.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{hofl:79}
J.~N. Holt and R.~Fletcher.
\newblock An algorithm for constrained non-linear least-squares.
\newblock {\em J. Inst. Maths. Applics.}, 23:449--463, 1979.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{kape:78}
L.~Kaufman and V.~Pereyra.
\newblock A method for separable nonlinear least squares problems with
  separable nonlinear equality constraints.
\newblock {\em SIAM Journal on Numerical Analysis}, 15:12--20, 1978.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{kopa:81}
S.~Kourouklis and C.~C. Paige.
\newblock A constrained approach to the general {Gauss-Markov} linear model.
\newblock {\em Journal of the American Statistical Association}, 76:620--625,
  1981.

\bibitem{lewe:70}
{\"O.}~Leringe and P.-\AA. Wedin.
\newblock A comparison between different methods to compute a vector $x$ which
  minimizes {$\|Ax-b\|_2$} when {$Gx=h$}.
\newblock Technical report, Department of Computer Science, Lund University,
  1970.

\bibitem{lots:83}
P.~L{\"o}tstedt.
\newblock Perturbation bounds for the linear least squares problem subject to
  linear inequality constraints.
\newblock {\em BIT}, 23:500--519, 1983.

\bibitem{lots:84}
P.~L{\"o}tstedt.
\newblock Solving the minimal least squares problem subject to bounds on the
  variables.
\newblock {\em BIT}, 24:206--224, 1984.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{mahd:81}
N.~Mahdavi-Amiri.
\newblock {\em Generally Constrained Nonlinear Least Squares and Generating
  Test Problems: Algorithmic Approach}.
\newblock PhD thesis, The John Hopkins University,, 1981.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{mova:91}
M.~Moonen and J.~Vandewalle.
\newblock A square root covariance algorithm for constrained recursive least
  squares estimation.
\newblock {\em Journal of VLSI Signal Processing}, 3:163--172, 1991.

\bibitem{olru:86}
D.~P. O'Leary and B.~W. Rust.
\newblock Confidence intervals for inequality-constrained least squares
  problems, with applications to ill-posed problems.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  7:473--489, 1986.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{schi:83}
K.~Schittkowski.
\newblock The numerical solution of constrained linear least-squares problems.
\newblock {\em IMA J. Numer. Anal.}, 3:11--36, 1983.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{schi:85}
K.~Schittkowski.
\newblock Solving constrained nonlinear least squares problems by a general
  purpose {SOP}-method.
\newblock Technical report, Institute f{\"u}r Informatik, Universit{\"a}t
  Stuttgart, 1985.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\bibitem{scst:79}
K.~Schittkowski and J.~Stoer.
\newblock A factorization method for the solution of constrained linear least
  squares problems allowing subsequent data changes.
\newblock {\em Numerische Mathematik}, 31:431--463, 1979.

\bibitem{shmw:87}
T.~J. Shepherd and J.~G. McWhirter.
\newblock A pipelined array for linearly constrained least squares
  optimization.
\newblock In T.~S. Durrani, J.~B. Abbiss, J.~E. Hudson, R.~W. Madan, J.~G.
  McWhirter, and T.~A. Moore, editors, {\em Mathematics in Signal Processing},
  pages 607--635, Oxford, 1987. Clarendon Press.
\newblock Cited in \cite{mova:91}.

\bibitem{stoe:71}
J.~Stoer.
\newblock On the numerical solution of constrained least-squares problems.
\newblock {\em SIAM Journal on Numerical Analysis}, 8:382--411, 1971.

\bibitem{vloa:85}
C.~F. Van~Loan.
\newblock On the method of weighting for equality constrained least squares.
\newblock {\em SIAM Journal on Numerical Analysis}, 22:851--864, 1985.

\bibitem{wedi:79}
P.-{\AA}. Wedin.
\newblock Notes on the constrained linear least squares problem. a new approach
  based on generalized inverses.
\newblock Technical Report UMINF--75.79, Institute of Information Processing,
  University of Ume\aa, 1979.

\bibitem{wedi:85}
P.-{\AA}. Wedin.
\newblock Perturbation theory and condition numbers for generalized and
  constrained linear least squares problems.
\newblock Technical Report UMINF--125.85, Institute of Information Processing,
  University of Ume\aa, 1985.

\bibitem{wedi:87}
P.-{\AA}. Wedin.
\newblock Perturbation theory and condition numbers for generalized and
  constrained least squares problems.
\newblock Technical Report S-901-87, Institute of Information Processing,
  University of Ume\aa, 1987.

\bibitem{wrho:85}
S.~J. Wright and J.~N. Holt.
\newblock Algorithms for nonlinear least squares with linear inequality
  constraints.
\newblock {\em SIAM Journal on Scientific and Statistical Computing},
  6:1033--1048, 1985.
\newblock Cited in {\AA ke Bj\"orck's} bibliography on least squares, which is
  available by anonymous ftp from {\tt math.liu.se} in {\tt pub/references}.

\end{thebibliography}
Newsgroups: sci.math.stat