CMPE 482
Home

CMPE 482 - Numerical Linear Algebra and Its Applications

Spring 2017

Instructor: Ali Taylan Cemgil
Bogazici University,
Department of Computer Engineering,
Istanbul, Turkey

Important announcement for taking CMPE482 in Spring 2017 for credit

  1. Prerequisite: Ability (or willingness to learn) programming in Octave and Python (numpy, scipy) and preparing reports on a jupyther notebook using latex and ipython. We won't teach you programming and programming projects are an important part.

  2. As CMPE482 is an elective course and there is no TA assigned this year, the class will be smaller this year.

  3. The projects will be turned in using git so you must be also familiar with it.

  4. CmpE students: Consent is required, I will accept only around 7-8 motivated students.

  5. Math undergraduates: In the past, many Math majors took the course but experience has shown that the lack of basic programming skills and the lack of computational thinking has been a major problem. This year, I will consider each consent request separately and I will be more selective. You need to have a high GPA (at least 2.75) and your transcript should reflect your programming background. I will approve your request with some delay (possibly by the last day of registration) and only if there are enough empty spots.

Administrative

  • Attendance and Participation in the lectures %10

  • Midterm %30

  • Final %30

  • 3 Projects %30

Final Project Bundle

Example Exams and projects

projects_spring2016.pdf

2014spring-cmpe482-mt1.pdf

2015spring-cmpe482-final.pdf

2015spring-cmpe482-mt1.pdf

Description

If you are interested in Machine learning, Data mining or Signal Processing, you shouldn't miss this course!

Numerical linear algebra provides a set of basic methods that are useful for developing algorithms for a diverse spectrum of applications in data processing. At its heart, this field studies algorithms for performing linear algebra computations, most notably matrix operations. These elegant algorithms provide often fundamental solutions to engineering and computational problems, such as

  1. Image and signal processing,

  2. Information retrieval

  3. Data mining,

  4. Machine learning,

  5. Bioinformatics

  6. Optimization

  7. Computational Finance,


and many related areas. Our goal in this course is to provide an overview of this important field, along with applications chosen from a broad range of topics related to data analysis.

Textbook

  1. Trefethen, Lloyd N. and Bau III, David; (1997). Numerical linear algebra. Philadelphia: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-361-9

Further References

  1. Golub, Gene H.; van Loan, Charles F. (1996), Matrix Computations, 3rd edition, Johns Hopkins University Press, ISBN 978-0-8018-5414-9

Lecture Slides

  1. Lecture 01,02,03 - Matrix-Vector Multiplication, Orthogonal Vectors and Matrices, Norms.pdf

  2. Lecture 04,05 - The SVD, More on the SVD.pdf

  3. Lecture 06,07,08,09 - Projectors, QR Factorization, Gram-Schmidt, Matlab.pdf

  4. Lecture 10,11 - Householder Triangularization, Least Squares Problems.pdf

  5. Lecture 12,13 - Conditioning, Floating Point Arithmetic.pdf

  6. Lecture 14,18,19 - Stability, Cond of LS prob, Stab of LS alg.pdf

  7. Lecture 24,25 - Eigenvalue Problems, Eigenvalue Algorithms.pdf

  8. Lecture 26-27, To hessenberg form, RQ, Power, inserve iterations.pdf

  9. Lecture 28,29 - QR Algorithm with and without Shifts.pdf

  10. Lecture 30,31 - Other Eigenvalue Algorithms, Computing the SVD.pdf

  11. Lecture 32 - Overview of Iterative Methods.pdf

  12. Lecture 33,34 - Arnoldi Iteration.pdf

  13. Conjugate Gradients

  • Thanks to all that have participated in the pi-Lab-sigma reading group series of Spring 2013!

  1. Ismail Ari

  2. Hakan Guldas

  3. Umut Simsekli

  4. Onur Gungor

  5. Beyza Ermis

  6. Deniz Akyildiz

  7. Can Kavaklioglu

  8. Baris Fidaner

  9. Alp Kindiroglu

  10. Cem Subakan

  11. Baris Kurt

Submissions

Computer Usage

We will use Octave and Python. See:

Starting Octave
octave --force-gui

Octave is a popular matlab clone. So, most (but not all) matlab material is useful

Topics

I Fundamentals

  • Matrix-Vector Multiplication

  • Orthogonal Vectors and Matrices

  • Vector and Matrix Norms

  • Singular Value Decomposition

  • Application: Document Retrieval, Latent Semantic indexing, Procrustes analysis

II QR Factorization

  • Projectors

  • Gram-Schmidt Orthogonalization, QR Factorization

  • MATLAB

  • Householder Triangularization

  • Least Square Problems

  • Application: Polynomial and Basis Regression

III Conditioning and Stability

  • Conditioning and Condition numbers

  • Floating Point Arithmetic

  • Stability

V Eigenvalues

  • Eigenvalue Problems

  • Overview of Eigenvalue Algorithms

  • Reduction to Hessenberg or Tridiagonal form

  • Rayleight Quotient, Inverse Iteration

  • QR algorithm without/with shifts

  • Computing the SVD

  • Application: Spectral Clustering, Image segmentation

Total Credits

3

Dedication

This course is dedicated to the memory of our collegue and friend Ismail Ari (1983-2013).