 |
CPSC 531F: Topics in Computer Science Theory:
Applications of Linear Algebra, Spring 2021
The class this term will be given FULLY ONLINE.
This page has the most up-to-date information on the course(s) and
supersedes any other document.
Materials below may have errors!
Errors will be corrected either here or in class.
If you are not attending my classes: use these materials at your
own risk!
| News |
There will be no further homework problems assigned this term, beyond
some optional problems in Section 6 uploaded on April 12
(the date of revision is April 9 at 6:41pm).
The only changes to the problems
on the Supplemental Notes and Homework will be corrections.
Please email me your solutions by April 25 at 11:59pm, and your slides
and/or notes or essay
by then
if you presented on April 13.
Supplemental Notes and Homework,
last revised April 12, 1:42pm.
Homework Problems
last revised April 9, 6:41pm.
Diversity news: February is Black History Month in Canada.
For example,
with your UBC CWL you can (free of charge) watch
I
Am Not Your Negro (James Baldwin, posthumously)
and read
some of Balwin,
Cornel West,
and many others.
Class hours are TuTh, 9:30-11am, starting January 12.
|
|---|
|
Overview |
Here is a
course overview, including a detailed list
of topics and course policy.
This course has two parts: (1) to review the theory and common applications
of eigenvalues/vectors to problems in computer science; and
(2) delve more deeply into some particular applications, notably
expanding graphs (graphs with ``good connectivity'' properties such
as being free of ``clusters'') and
some aspects of ``Monte Carlo'' Markov chains.
Of course, we will point out the limitations of such techniques, as well.
The amount of time spend on various topics will depend
in part on the interests of the students.
The course grade will be based on three homework problem sets; some problems
will be assigned every class or two.
In lieu of the last problem set, students may write
short essay on an application of linear algebra of their choosing.
|
|---|
|
Fully Online |
This term (January to April, 2021), the course will be
fully online.
We will use
UBC's Canvas system
to communicate, sign into Zoom, and
to access recordings of lectures.
All lectures will be recorded (barring technological problems) and
will be available via Canvas.
Board scans of all lectures will be posted below.
|
|---|
|
References |
There is no single reference for the class.
I am maintaining a
separate webpage of useful
references for this course.
Here are the main ones.
Aside from this, here are some other important references.
-
Expanders:
Expander graphs and their applications, by Hoory, Linial, Wigderson
(123 page survey article, 2008 AMS Conant Prize winner),
-
Markov Chains:
Markov Chains and Mixing Times, by Levin, Peres, Wilmer,
-
Coding for Constrained Systems:
See these unpublished course notes of Marcus, Roth, and Siegel, Chapter 1, for a description of various data constraints.
The article
Algorithms for sliding block codes - Etc., by Adler, Coppersmith, and Hassner uncovered the connection between symbolic dynamics and constrained coding.
On synchronous variable length coding for discrete noiseless
ch(r)annels, by Franaszek
is an early (1969) of constrained coding and so-called "Franaszek codes."
|
|---|
|
Readings and Boards Scans |
Board scans will appear here.
Tentative topics are listed below (see
the course overview for a more detailed outline).
-
Roughly 5 weeks:
Introduction to some theory and applications of linear algebra.
Tentative topics: Symmetric matrices in graph theory;
review of linear algebra and examples;
positive semidefinite matrices in graph theory and beyond;
symmetric matrices in the SVD and applications;
symmetric matrices in projections;
Markov matrices and biorthogonal decomposition;
reversible Markov chains;
(briefly) unitary matrices in quantum mechanics and computing;
other topics.
Board scans:
01_12 (overview, notation for matrices,
digraphs, and Markov chains).
01_14 (digraph examples,
similarity, motivation for
diagonalizability).
01_19 (Fibonacci graph and (2,7)-constrained
data graph, eigenvalues/vectors and characteristic polynomials, some
examples.)
01_21 (eigenpairs for C_n, circulant
matrices, trace and determinant in the characteristic polynomial,
generalized eigenspaces and Jordan matrices, Jordan canonical form--just
examples and general result--without proofs);
01_26 (Boolean hypercube, orthonormal
eigenbases writing a matrix as sum lambda_i v_i (v_i)^T,
orthogonal matrices in diagonalization,
cartesian product of graphs);
01_28 (Recurrence equations and Jordan
blocks, powers of Jordan blocks, orthogonal matrices and orthonormal
bases, the 3x3 all 1's matrix and real o.n. bases versus the
roots of unity basis);
02_02 (Complex dot product and C_3 and C_n,
complex orthonormalization in circulant matrices, cartesian product of
graphs and their eigenvalues).
-
Roughly 8 weeks:
Detailed discussion of applications.
Tentative topics: expanders; Markov chains;
reversible Markov chains; relativization and refinement of
graphs and Markov chains; PageRank; etc.
-
Regular graphs and the Expander Mixing Lemma
Board scans:
02_04 (d-regular graphs,
Kronecker product = matrix tensor product, Boolean n-cube again and weights
and bipartiteness,
multiplicity of d and -d in the eigenvalues d-regular graphs,
block matrices, the
analog for some 2x2 MC's (Markov chains), connected and strongly connected
components, irreducible MC's and general MC's).
02_09 (Proof of Theorem 4.11 in the
Homework and Supplemental Notes, eigenvalues and edge counts, in particular
the
Expander Mixing Lemma).
02_11 (continuation of Theorem 4.11,
including: eigenvalues of symmetric matrices and their L^2 operator
norm, Section 4.2 and start of 4.3 of Homework and Supplemental Notes).
02_23 (review of symmetric matrices,
Rayleigh quotients, orthogonal matrices, projections, finish proof of
the Expander mixing lemma; start reversible Markov chains and the
dolphin example).
-
Markov Chains: More Examples, Mixing Time, and Reversible Chains
Board scans:
02_25 (espilon-mixing time of a Markov
chain, total variation, card shuffling and the symmetric group,
groups).
03_02 (more on the L^2-operator
norm and matrix norms, relevance to Exercise 4.2,
the formula for the inverse of I-A for
A with ||A^r||<1 for some r, negative powers of Jordan matrices
chain, epsilon-mixing times and periodic Markov chains (e.g., C_3)
with no finite mixing time, the mixing time of the Boolean hypercube).
03_04 (more examples of Markov chains:
2 state examples and mixing times, the Boolean hypercube (again),
"lazy" forms of a chain, reversible chains (again), Markov chain
associated to a graph (which is reversible), start Metropolis
algorithm: special case of chains created from d-regular graphs).
03_09 (reversible chains: (1) as time
reversible, (2) as useful to create Metropolis chains, and (3) as
self-adjoint with respect to inner product weighted by stationary
distribution and its reciprocal; inner products on R^n and self-adjoint
operators; example of 2 x 2 chain and orthonormality of eigenvectors
with respect to weighted inner products).
-
Some Theory: Symmetric Matrices and Self-Adjoint Operators
Board scans:
03_11 (review of norms and weighted
norms and inner products, comments on HW 1, Rayleight quotients,
maximizing continuous functions on the sphere, projections on
inner product spaces, variational proof
that Rayliegh quotient maximum is attained on eigenvectors).
03_16 (review of inner products,
a weighted inner product arising from different units of measurement,
continuing the variational argument to find all eigenvpairs for the
Rayleigh quotient of a self-adjoint map).
03_18 (comments on homework, review
variational proof of ON eigenbasis for self-adjoint operators,
start SVD (singular-value decomposition) with best rank 1
approximation and the Frobenius norm).
03_23 (overview of matrix decompositions,
reducing dimension of data, continuation of SVD by variational
approach, alternative SVD approach by eigenvectors of A^T A).
03_25 (another variational method:
least squares, comparison of variational methods in
Rayleigh quotient and best rank one approximation: both identify
critical points (stationary values) attained at eigenvectors,
SVD and dimension reduction).
03_30 (second proof of ON eigenbasis
with real eigenvalues for symmetric matrices: true for symmetric
matrices with distinct eigenvalues via complex inner product,
homotopies of matrices and
distinct eigenvalues, limit argument).
04_01 (third proof of ON eigenbasis
with real eigenvalues for symmetric matrices: Schur decomposition
(statement and quick theoretical proof), normal matrices,
normal upper triangular matrices are diagonal; start
Perron-Frobenius theorem).
-
Perron-Frobenius Theorem and Applications
Board scans:
04_06 (run-length constrained data,
Perron-Frobenius eigenvalue defined as maximum stretch of every
component, power method, example on Fibonacci graph, capacity of a graph,
using Fibonacci graph to encode roughly 2 bits of general data
to 3 bits of Fibonacci constrained data).
04_08 (review coding in run-length
constrained data, failure of power method on C_4 and periodicity,
another periodicity example, ideas behind proof of Perron-Frobenius
theorem).
|
|---|
| Homework and Supplemental Notes
|
I will be assigning some problems from these
Supplemental Notes and Homework,
last revised April 12, 1:42pm.
This document will be revised throughout the term
and is a reference: in class we will cover only
some of the topics, and often in a different order.
Here is the current list of
Homework Problems,
last revised April 9, 6:41pm;
I will be adding problems as we cover new topics.
The first set will be based on class Jan 12 - Feb 4; you should aim to
submit it by Feb 28.
|
|---|
| Essay Topics |
Instead of the third problem set, students can
write short essay on an application of linear algebra of their choice.
I will recommend some topics here.
|
|---|
|
Piazza and Office Hours |
There will be an online discussion of this course on
www.piazza.com; use
this link
to sign up.
Please post all questions related to the course material
to our piazza site.
For now I will hold office hours by appointment; if you'd like to meet,
please email me and let me know when you are free over the next few
weekdays. If/when I get too many requests, I'll revert to fixed
office hours.
All office hours can be reached via Canvas.
|
|---|
| Diversity and Equity |
UBC is trying in earnest to
encourage
diversity and
alleviate biases and inequities
to which some members of its community are subjected;
this includes, for example, UBC's
Indian Residential School History and Dialogue Center, and well as
the Computer Science Department's various programs described on its
Diversity in CS
webpage.
I try to act reasonably free of bias; for example,
I do not view
sexual orientation or gender as
set in stone from birth or as classified by some fixed, finite set of
choices; I try
to use language accordingly.
I will undoubtedly
goof upon occasion, and I welcome feedback on these and related matters.
|
|---|
|