SEE

Lecture 9 - Least-Norm Solution

Expand/Collapse Video
• Bookmarks
• 00:00:24

Least-norm Solution

• 00:12:14

Least-norm Solution Via QR Factorization

• 00:14:31

Derivation Via Lagrange Multipliers

• 00:17:47

Example: Transferring Mass Unit Distance

• 00:27:47

Relation To Regularized Least-squares

• 00:32:39

General Norm Minimization With Equality Constraints

• 00:44:01

Autonomous Linear Dynamical Systems

• 00:53:25

Block Diagram

Show All

Course Description

Introduction to applied linear algebra and linear dynamical systems, with applications to circuits, signal processing, communications, and control systems.

Topics include: Least-squares aproximations of over-determined equations and least-norm solutions of underdetermined equations. Symmetric matrices, matrix norm and singular value decomposition. Eigenvalues, left and right eigenvectors, and dynamical interpretation. Matrix exponential, stability, and asymptotic behavior. Multi-input multi-output systems, impulse and step matrices; convolution and transfer matrix descriptions. Control, reachability, state transfer, and least-norm inputs. Observability and least-squares state estimation.

Prerequisites: Exposure to linear algebra and matrices (as in Math. 103). You should have seen the following topics: matrices and vectors, (introductory) linear algebra; differential equations, Laplace transform, transfer functions. Exposure to topics such as control systems, circuits, signals and systems, or dynamics is not required, but can increase your appreciation.

Instructor

Boyd, Stephen

Stephen P. Boyd is the Samsung Professor of Engineering, and Professor of Electrical Engineering in the Information Systems Laboratory at Stanford University. His current research focus is on convex optimization applications in control, signal processing, and circuit design.

Professor Boyd received an AB degree in Mathematics, summa cum laude, from Harvard University in 1980, and a PhD in EECS from U. C. Berkeley in 1985. In 1985 he joined the faculty of Stanford’s Electrical Engineering Department. He has held visiting Professor positions at Katholieke University (Leuven), McGill University (Montreal), Ecole Polytechnique Federale (Lausanne), Qinghua University (Beijing), Universite Paul Sabatier (Toulouse), Royal Institute of Technology (Stockholm), Kyoto University, and Harbin Institute of Technology. He holds an honorary doctorate from Royal Institute of Technology (KTH), Stockholm.

Professor Boyd is the author of many research articles and three books: Linear Controller Design: Limits of Performance (with Craig Barratt, 1991), Linear Matrix Inequalities in System and Control Theory (with L. El Ghaoui, E. Feron, and V. Balakrishnan, 1994), and Convex Optimization (with Lieven Vandenberghe, 2004).

Professor Boyd has received many awards and honors for his research in control systems engineering and optimization, including an ONR Young Investigator Award, a Presidential Young Investigator Award, and an IBM faculty development award. In 1992 he received the AACC Donald P. Eckman Award, which is given annually for the greatest contribution to the field of control engineering by someone under the age of 35. In 1993 he was elected Distinguished Lecturer of the IEEE Control Systems Society, and in 1999, he was elected Fellow of the IEEE, with citation: “For contributions to the design and analysis of control systems using convex optimization based CAD tools.” He has been invited to deliver more than 30 plenary and keynote lectures at major conferences in both control and optimization.

In addition to teaching large graduate courses on Linear Dynamical Systems, Nonlinear Feedback Systems, and Convex Optimization, Professor Boyd has regularly taught introductory undergraduate Electrical Engineering courses on Circuits, Signals and Systems, Digital Signal Processing, and Automatic Control. In 1994 he received the Perrin Award for Outstanding Undergraduate Teaching in the School of Engineering, and in 1991, an ASSU Graduate Teaching Award. In 2003, he received the AACC Ragazzini Education award, for contributions to control education, with citation: “For excellence in classroom teaching, textbook and monograph preparation, and undergraduate and graduate mentoring of students in the area of systems, control, and optimization.”

Handouts

Lecture Handouts:

Handout NameHandout Usage
Overview Lecture 1
Linear functions Lecture 2-3
Linear algebra review Lectures 3-4
Orthonormal sets of vectors and QR factorization Lecture 4-5
Least-squares Lectures 5-6
Least-squares applications Lectures 6-7
Regularized least-squares and Gauss-Newton method Lectures 7-8
Least-norm solutions of underdetermined equations Lectures 8-9
Autonomous linear dynamical systems Lecture 9
Solution via Laplace transform and matrix exponential Lecture 11
Eigenvectors and diagonalization Lectures 12-13
Jordan canonical form Lectures 13-14
Linear dynamical systems with inputs and outputs Lectures 14-15
Example: Aircraft dynamics Lecture 15
Symmetric matrices, quadratic forms, matrix norm, and SVD Lectures 15-17
SVD applications Lectures 17-18
Example: Quantum mechanics Lecture 18
Controllability and state transfer Lectures 18-20
Observability and state estimation Lecture 20
Summary and final comments Lecture 20

 Matrix primer notes Crimes against matrices Basic notation Least squares and least norm solutions using Matlab Solving general linear equations using Matlab Low rank approximation and extremal gain problems

Assignments

All numbered exercises are from the EE263 homework problems.
You will sometimes need to download Matlab files, see Software below.

AssignmentExercisesDue Date
Homework 1 2.1–2.4, 2.6, 2.9, 2.12, and an additional exercise Lecture 4
Homework 2 3.2, 3.3, 3.10, 3.11, 3.16, 3.17, and three additional exercises Lecture 6
Homework 3 2.17, 3.13, 4.1–4.3, 5.1, 6.9, and two additional exercises Lecture 8
Homework 4 5.2, 6.2, 6.5, 6.12, 6.14, 6.26, 7.3, 8.2 Lecture 10
Homework 5 10.2, 10.3, 10.4, and an additional exercise Lecture 13
Homework 6 9.9, 10.5, 10.6, 10.8, 10.14, 11.3, and 11.6a Lecture 14
Homework 7 10.9, 10.11, 10.19, 11.13, 12.1, 13.1, and an additional exercise Lecture 16
Homework 8 13.17, 14.2, 14.3, 14.4, 14.6, 14.8, 14.9, 14.11, 14.13, 14.21, 14.33, and an additional exercise
Please note: (a) you have two weeks to do these, and (b) some of them are very straightforward.
Lecture 18
Homework 9 14.16, 14.26, 15.2, 15.3, 15.6, 15.8, 15.10, and 15.11 Lecture 20

Exams

 Practice Midterm Questions Solutions Midterm Questions Solutions Practice Final Questions Solutions Final Questions Solutions

Software

Matlab Files

 beam_estim_data.mht color_perception.mht curve_smoothing.mht gate_sizing_data.mht line_conv_data.mht line_pixel_length.mht linexp_data.mht max_min_init_state.mht mc_data.mht nleq_data.mht one_bad_sensor.mht opt_bin_data.mht problem_10_14_data.mht ri_data.mht simplefitdata.mht smooth_interpolation.mht sysid_data.mht temp_prof_data.mht time_comp_data.mht tmeasure.mht tomodata.mht tv_data.mht uie_data.mht

Show All

Lecture 1

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 17 min Topics: Overview Of Linear Dynamical Systems, Why Study Linear Dynamical Systems?, Examples Of Linear Dynamical Systems, Estimation/Filtering Example, Linear Functions And Examples

Lecture 2

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 6 min Topics: Linear Functions (Continued), Interpretations Of Y=Ax, Linear Elastic Structure, Example, Total Force/Torque On Rigid Body Example, Linear Static Circuit Example, Illumination With Multiple Lamps Example, Cost Of Production Example, Network Traffic And Flow Example, Linearization And First Order Approximation Of Functions

Lecture 3

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 19 min Topics: Linearization (Continued), Navigation By Range Measurement, Broad Categories Of Applications, Matrix Multiplication As Mixture Of Columns, Block Diagram Representation, Linear Algebra Review, Basis And Dimension, Nullspace Of A Matrix

Lecture 4

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 14 min Topics: Nullspace Of A Matrix(Continued), Range Of A Matrix, Inverse, Rank Of A Matrix, Conservation Of Dimension, 'Coding' Interpretation Of Rank, Application: Fast Matrix-Vector Multiplication, Change Of Coordinates, (Euclidian) Norm, Inner Product, Orthonormal Set Of Vectors

Lecture 5

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 15 min Topics: Orthonormal Set Of Vectors, Geometric Interpretation, Gram-Schmidt Procedure, General Gram-Schmidt Procedure, Applications Of Gram-Schmidt Procedure, 'Full' QR Factorization, Orthogonal Decomposition Induced By A, Least-Squares

Lecture 6

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 16 min Topics: Least-Squares, Geometric Interpretation, Least-Squares (Approximate) Solution, Projection On R(A), Least-Squares Via QR Factorization, Least-Squares Estimation, Blue Property, Navigation From Range Measurements, Least-Squares Data Fitting

Lecture 7

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 16 min Topics: Least-Squares Polynomial Fitting, Norm Of Optimal Residual Versus P, Least-Squares System Identification, Model Order Selection, Cross-Validation, Recursive Least-Squares, Multi-Objective Least-Squares

Lecture 8

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 16 min Topics: Multi-Objective Least-Squares, Weighted-Sum Objective, Minimizing Weighted-Sum Objective, Regularized Least-Squares, Laplacian Regularization, Nonlinear Least-Squares (NLLS), Gauss-Newton Method, Gauss-Newton Example, Least-Norm Solutions Of Undetermined Equations

Lecture 9

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 9 min Topics: Least-Norm Solution, Least-Norm Solution Via QR Factorization, Derivation Via Langrange Multipliers, Example: Transferring Mass Unit Distance, Relation To Regularized Least-Squares, General Norm Minimization With Equality Constraints, Autonomous Linear Dynamical Systems, Block Diagram

Lecture 10

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 12 min Topics: Examples Of Autonomous Linear Dynamical Systems, Finite-State Discrete-Time Markov Chain, Numerical Integration Of Continuous System, High Order Linear Dynamical Systems, Mechanical Systems, Linearization Near Equilibrium Point, Linearization Along Trajectory

Lecture 11

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 9 min Topics: Solution Via Laplace Transform And Matrix Exponential, Laplace Transform Solution Of X_^ = Ax, Harmonic Oscillator Example, Double Integrator Example, Characteristic Polynomial, Eigenvalues Of A And Poles Of Resolvent, Matrix Exponential, Time Transfer Property

Lecture 12

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 14 min Topics: Time Transfer Property, Piecewise Constant System, Qualitative Behavior Of X(T), Stability, Eigenvectors And Diagonalization, Scaling Interpretation, Dynamic Interpretation, Invariant Sets, Summary, Markov Chain (Example)

Lecture 13

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 13 min Topics: Markov Chain (Example), Diagonalization, Distinct Eigenvalues, Digaonalization And Left Eigenvectors, Modal Form, Diagonalization Examples, Stability Of Discrete-Time Systems, Jordan Canonical Form, Generalized Eigenvectors

Lecture 14

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 18 min Topics: Jordan Canonical Form, Generalized Modes, Cayley-Hamilton Theorem, Proof Of C-H Theorem, Linear Dynamical Systems With Inputs & Outputs, Block Diagram, Transfer Matrix, Impulse Matrix, Step Matrix

Lecture 15

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 9 min Topics: DC Or Static Gain Matrix, Discretization With Piecewise Constant Inputs, Causality, Idea Of State, Change Of Coordinates, Z-Transform, Symmetric Matrices, Quadratic Forms, Matrix Nom, And SVD, Eigenvalues Of Symmetric Matrices, Interpretations Of Eigenvalues Of Symmetric Matrices, Example: RC Circuit

Lecture 16

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 13 min Topics: RC Circuit (Example), Quadratic Forms, Examples Of Quadratic Form, Inequalities For Quadratic Forms, Positive Semidefinite And Positive Definite Matrices, Matrix Inequalities, Ellipsoids, Gain Of A Matrix In A Direction, Matrix Norm, Properties Of Matrix Norm

Lecture 17

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 17 min Topics: Gain Of A Matrix In A Direction, Singular Value Decomposition, Interpretations, Singular Value Decomposition (SVD) Applications, General Pseudo-Inverse, Pseudo-Inverse Via Regularization, Full SVD, Image Of Unit Ball Under Linear Transformation, SVD In Estimation/Inversion, Sensitivity Of Linear Equations To Data Error

Lecture 18

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 15 min Topics: Sensitivity Of Linear Equations To Data Error, Low Rank Approximations, Distance To Singularity, Application: Model Simplification, Controllability And State Transfer, State Transfer, Reachability, Reachability For Discrete-Time LDS

Lecture 19

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 10 min Topics: Reachability, Controllable System, Lest-Norm Input For Reachability, Minimum Energy Over Infinite Horizon, Continuous-Time Reachability, Impulsive Inputs, Least-Norm Input For Reachability

Lecture 20

 Watch Online: Download: Right Click, and Save As Duration: 1 hr 9 min Topics: Continuous-Time Reachability, General State Transfer, Observability And State Estimation, State Estimation Set Up, State Estimation Problem, Observability Matrix, Least-Squares Observers, Some Parting Thoughts..., Linear Algebra, Levels Of Understanding, What's Next