Changeset 1455

Timestamp:

Aug 10, 2004, 1:08:40 PM (22 years ago)

Author:

Paul Price

Message:

Major changes to minimization.

File:

• trunk/doc/pslib/psLibSDRS.tex (modified) (3 diffs)

trunk/doc/pslib/psLibSDRS.tex

@@ -1 @@
-%%% $Id: psLibSDRS.tex,v 1.64 2004-08-09 23:22:58 price Exp $
+%%% $Id: psLibSDRS.tex,v 1.65 2004-08-10 23:08:40 price Exp $
 \documentclass[panstarrs,spec]{panstarrs}
 
@@ -32 +32 @@
 01 & 2004 May 19 & Extensive modifications, see appendix \\ \hline
 02 & 2004 Jun 22 & Incorporation of Bugzilla PRs (up to 69) \\ \hline
-03 & 2004 Aug 09 & Adding convolution, splines, chebyshevs \\
-   &             & (modified polynomials), ImageTrim for Phase 2 \\ \hline
+03 & 2004 Aug 10 & Adding convolution, splines, chebyshevs \\
+   &             & (modified polynomials), ImageTrim for Phase 2. \\
+   &             & Changed minimization. \\ \hline
 \RevisionsEnd
 
@@ -2084 +2085 @@
 We require a general minimization routine, a routine that will
 specifically minimize $\chi^2$ given a list of data with associated
-errors, and a function that will analytically determine the best
-polynomial fit by minimizing $\chi^2$.  
-
-Consider a function \code{myFunction} which is a function of a
-collection of parameters \code{params} and coordiate vector
-\code{coord}, and returns a single floating point value.  We define
-\code{psMinimize}, which determines the parameters of
-\code{myFunction} which minimize the function for the coordinate
-\code{coord}.  The returned vector must be the same length as the
-vector argument to the input function.
-\begin{verbatim}
-float myFunction (psVector *params, psVector *coord);
-float myFuncDeriv (psVector *params, psVector *coord);
-psVector *psMinimize(psVector *restrict initialGuess, 
-                     float (*myFunction)(psVector *, psVector *),
-                     float (*myFuncDeriv)(psVector *, psVector *),
-                     const psVector *restrict coord,
-                     const psVector *restrict paramMask);
-\end{verbatim}
-\code{psMinimize} determines and returns the vector that minimizes the
-specified function.  It takes as input a function, \code{myFunction},
-an initial guess for the vector that minimizes the function,
-\code{initialGuess}, the current coordiate \code{coord}, and an
-optional mask for the vector elements (function parameters) to
-minimize, \code{paramMask} (all parameters are fit if \code{NULL}).
-Note that \code{paramMask} must be of type \code{psU8}, while
-\code{params} must be of type \code{psF32}.  The optional function,
-\code{myFuncDeriv} returns the derivative of the function.  This
-function must be valid only for types \code{psF32}, \code{psF64}.
-
-\begin{verbatim}
-psVector *psMinimizeChi2(psVector *restrict initialGuess,
-                         float (*evalModel)(psVector *, psVector *),
-                         const psVector *restrict domain,
-                         const psVector *restrict data,
-                         const psVector *restrict errors,
-                         const psVector *restrict paramMask,
-                         float *ChiSq);
-\end{verbatim}
-\code{psMinimizeChi2} fits a model to observations by minimizing
-$\chi^2$, returning the best-fit parameters.  The input parameters are
-a function that evaluates the model for a specified domain, given the
-parameters, \code{evalModel}; a list of observations, (\code{domain},
-\code{data}, and \code{errors}); an initial guess at the best-fit
-parameters, \code{initialGuess} which is returned with the best-fit
-parameters, and an optional mask specifying which parameters are to be
-fit, \code{paramMask}, which must be of type \code{psU8}.  All
-parameters are fit if this vector is \code{NULL}.  This
-function must be valid only for types \code{psF32}, \code{psF64}.
+errors, and functions that will analytically determine the best
+polynomial and spline fits by minimizing $\chi^2$.
+
+We specify two minimization engines, Levenberg-Marquardt and Powell,
+since the former is relatively robust, but requires derivatives to be
+known, while the latter does not always obtain the best fit but does
+not require derivatives to be known.
+
+In both cases, we need to be able to set the maximum number of
+iterations (\code{maxIter}) and the maximum tolerance (\code{tol}) for
+convergence, in addition to having some basic information on the
+results and quality of the minimization: the value of the function at
+the minimum (\code{value}), the number of iterations performed
+(\code{iter}) and last change in tolerance before returning
+(\code{lastDelta}).
+
+\begin{verbatim}
+typedef struct {
+    const int maxIter;                  ///< Maximum number of iterations
+    const float tol;                    ///< Tolerance to reach
+    float value;                        ///< Value after minimization
+    int iter;                           ///< Actual number of iterations performed
+    float lastDelta;                    ///< Last change before quitting
+} psMinimization;
+\end{verbatim}
+
+The corresponding allocator is:
+\begin{verbatim}
+psMinimization *psMinimizationAlloc(int maxIter, float tol);
+\end{verbatim}
+
+\subsubsection{Levenberg-Marquardt}
+
+Consider a function of a collection of parameters, \code{params}, and
+(possibly several) coordinate vectors (which we represent as an array
+of vectors), \code{coord}, which returns a single floating point value
+which is the value of the function given the parameters and coordinate
+vectors, along with the derivatives of the function with respect to
+each of the parameters:
+\begin{verbatim}
+typedef float (*psMinimizeLMFunc)(psVector *deriv, const psVector *params, const psArray *coords);
+\end{verbatim}
+
+Then \code{psMinimizeLM} shall mimimize the specified function,
+\code{func}, using the Levenberg-Marquardt method:
+
+\begin{verbatim}
+bool psMinimizeLM(psMinimization *min, psMatrix *covar, psVector *params, const psVector *paramMask,
+                  const psArray *coords, psMinimizeLMFunc func);
+\end{verbatim}
+
+The function shall return \code{false} in the event that there was an
+error (bad input, too many iterations), and also call \code{psError}.
+
+The minimization specification, \code{min}, shall be modified with the
+\code{value}, \code{iter} and \code{lastDelta} members updated with
+the values appropriate from the minimization.
+
+On calling the minimizer, \code{params} shall consist of a ``best
+guess'' for the parameters that minimize the input function,
+\code{func}.  On successful completion, the input parameters,
+\code{params}, shall be updated with the values that minimize the
+input function.  The function shall also update the covariance matrix,
+\code{covar}, in the event that it is non-\code{NULL}.  The function
+shall generate in error in the event that \code{covar} is not a square
+matrix with size matching that of \code{params}.
+
+Parameters that have a corresponding \code{paramMask} entry of
+\code{0} are to be held fixed by the minimizer.  It shall be an error
+for \code{paramMask} not to be of the same dimension as \code{params}.
+
+The \code{coords} are not handled by the minimizer, except to be
+passed to the function as additional input, and it is the
+responsibility of the function to interpret these.
+
+\code{paramMask} must be of type \code{psU8}, while \code{params} must
+be of type \code{psF32}.  The \code{func} function must be valid only
+for types \code{psF32}, \code{psF64}.
+
+\subsubsubsection{Pre-defined Functions for LM}
+
+We define some commonly used functions for use with the LM
+minimization, used for the purpose of performing $\chi^2$ fitting:
+
+\begin{verbatim}
+psMinimizeLMFunc psMinimizeLMChi2Gauss1D;
+psMinimizeLMFunc psMinimizeLMChi2Gauss2D;
+\end{verbatim}
+
+\code{psMinimizeChi2LMGauss1D} shall take, as \code{params}, the
+normalization, center, and standard deviation of a Gaussian to be fit
+to the data.  The data in the \code{coords} shall consist of vectors
+for each of \code{x}, \code{y}, and \code{yErr}.  If the \code{yErr}
+is missing, or \code{NULL}, then the errors shall be taken to be
+unity, for the purpose of fitting where the errors are all identical
+(and possibly unknown).  If the \code{x}, \code{y} or \code{yErr} (if
+supplied) vectors are of differing lengths, the function shall
+generate a warning and truncate the lengths to match the shortest.
+
+\code{psMinimizeLMChi2Gauss1D} shall return the $\chi^2$ value for the
+specified Gaussian as a model for the supplied data, along with the
+derivatives of the $\chi^2$ with respect to each of the parameters.
+
+\code{psMinimizeChi2LMGauss2D} shall take, as \code{params}, the
+normalization, center (two values), standard deviation (two values)
+and position angle of a 2-dimensional Gaussian to be fit to the data.
+The data in the \code{coords} shall consist of vectors for each of
+\code{x}, \code{y}, \code{z} and \code{zErr}.  If the \code{zErr} is
+missing, or \code{NULL}, then the errors shall be taken to be unity,
+for the purpose of fitting where the errors are all identical (and
+possibly unknown).  If the \code{x}, \code{y}, \code{z} or \code{zErr}
+(if supplied) vectors are of differing lengths, the function shall
+generate a warning and truncate the lengths to match the shortest.
+
+\code{psMinimizeLMChi2Gauss2D} shall return the $\chi^2$ value for the
+specified Gaussian as a model for the supplied data, along with the
+derivatives of the $\chi^2$ with respect to each of the parameters.
+
+\subsubsection{Powell}
+
+As for the LM minimizer, consider a function of a collection of
+parameters, \code{params}, and (possibly several) coordinate vectors
+(which we represent as an array of vectors), \code{coord}, and returns
+a single floating point value which is the value of the function given
+the parameters and coordinate vectors, but now the derivatives are not
+known:
+\begin{verbatim}
+typedef float (*psMinimizePowellFunc)(const psVector *params, const psArray *coords);
+\end{verbatim}
+
+Then \code{psMinimizePowell} shall mimimize the specified function,
+\code{func}, using the Powell method:
+
+\begin{verbatim}
+bool psMinimizePowell(psMinimization *min, psVector *params, const psVector *paramMask,
+                      const psArray *coords, psMinimizePowellFunc func);
+\end{verbatim}
+
+The inputs and general behavior of this function is the same as for
+\code{psMinimizeLM}, except for the absence of the covariance matrix,
+\code{covar}.
+
+\subsubsubsection{Minimizing $\chi^2$ with Powell}
+
+We require a front-end to the Powell minimizer to allow fitting
+general functions to data.
+
+\begin{verbatim}
+typedef psVector* (*psMinimizeChi2PowellFunc)(const psVector *params, const psArray *coords);
+
+bool psMinimizeChi2Powell(psMinimization *min, psVector *params, const psVector *paramMask,
+                          const psArray *coords, const psVector *value, const psVector *error,
+                          psMinimizeChi2PowellFunc model);
+\end{verbatim}
+
+The inputs and general behavior of \code{psMinimizeChi2Powell} is
+similar as for \code{psMinimizePowell}, with the exception that
+instead of being provided the function to be minimized, it is provided
+a model to fit and must calculate the $\chi^2$ to be minimized itself.
+
+For this purpose, \code{value} shall contain measured values at the
+coordinates, and \code{error} may either be non-\code{NULL}, in which
+case it contains the errors in the measured values; otherwise the
+errors shall assumed to be unity for the purpose of fitting where the
+errors are all identical (and possibly unknown).
+
+Furthermore, the \code{model} function provided by the user shall
+return a vector of values (instead of a single value, as was the case
+for \code{psMinimizePowell}), corresponding to the model predictions
+to be compared against the measured values.  If the lengths of the
+\code{value}, \code{error} (if provided) vectors and the vector
+returned by the \code{model} function differ, then
+\code{psMinimizeChi2Powell} shall generate a warning, truncate the
+vectors to the length of the shortest and proceed (only one error
+should be generated per call).
+
+\subsubsection{Analytical fits}
 
 \begin{verbatim}