Lecture 9 - Least-Norm Solution

Expand/Collapse Video

Course Details

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

FPO

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.”

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

Course Sessions (20):

Show All

Lecture 1

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 2

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 3

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 4

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 5

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 6

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 7

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 8

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 9

Watch Online: Download:
Right Click, and Save As
Duration:
Now Playing Download 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

Transcripts

Lecture 10

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 11

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 12

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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)

Transcripts

Lecture 13

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 14

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 15

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 16

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 17

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 18

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 19

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts

Lecture 20

Watch Online: Download:
Right Click, and Save As
Duration:
Watch Now Download 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

Transcripts