Nonlinear Regression With Linear Constraints: An Extension of the Magnified Diagonal Method

ABSTRACT

A syntax-directed picture analysis system based on a formal picture description scheme is described. The system accepts a description of a set of pictures in terms of a grammar generating strings in a picture description language; the grammar is explicitly used to direct the analysis or parse, and to control the calls on pattern classification routines for primitive picture components. Pictures are represented by directed graphs with labeled edges, where the edges denote elementary picture components and the graph connectivity mirrors the picture component connectivity; blank and don't care “patterns” allow the description of simple relations between visible patterns. The bulk of the paper is concerned with the picture parsing algorithm which is an n-dimensional analog of a classical top-down string parser, and an application of an implemented system to the analysis of spark chamber film. The potential benefits of this approach, as demonstrated by the application, include ease of implementation and modification of picture processing systems, and simplification of the pattern recognition problem by automatically taking advantage of contextual information.

REFERENCES

• 1: George E. Forsythe , Gene H. Golub, Maximizing a second-degree polynomial on the unit sphere, Stanford University, Stanford, CA, 1965
• 2: LEVENBERG, K. A method for the solution of certain non-linear problems in least squares. Quart. Appl. Math. 2, 2 (July 1944), 164---168.
• 3: MARQUARDT, D.W. An algorithm for least-squares determination of non-linear parammeters. SIAM J. Appl. Math. 11, 2 (June 1963), 431-441.
• 4: MEETER, D.A. On a theorem used in non-linear least squares. SIAM J. Appl. Math. 1~ (Sept. 1966), 1176-1179.
• 5: 1VIORRISON, D. D. Methods for non-linear least squares problems and convergence proofs. Tracking Programs and Orbit Determination, Proc. Jet Propulsion Laboratory Seminar, 1960, pp. 1-9. (Available from Space Technology Lab., Redondo Beach, Calif.) B. Quadratic Programming
• 6: HADLEY, G. Nonlinear and Dynamic Programming. Addison-Wesley, Reading, Mass., 1964.
• 7: HILDRETH, C. A quadratic programming procedure. Nay. Res. Logistics Quart. 14 (1957), 79-85.
• 8: HOUTHAKKER, H.S. The capacity method of quadratic programming. Econometrica ~8 (1960), 62-87.
• 9: MARKOWITZ, H. Portfolio Selection (Cowles Foundation Monograph No. 16). Wiley, New York, 1959.
• 10: WOLFE, P. The simplex method for quadratic programming. Econometrica ~7 (1959), 382--398.
• 11: SHRAGER, R. A quadratic programming algorithm. (Submitted for publication.)

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations

General Terms:
Performance, Theory