18.065/18.0651  Matrix Methods

HW 7 now due May 18th (because of MIT level policy on HWs) + updated HW7

HW 7 is now due by 12.30 pm on May 18th instead of May 20th. The reason for the change is that pursuant to the MIT policy:

Per MIT's faculty rules and regulations section 2.53:

"For each subject in which there is testing during the final examination period, no assignment may fall due after the Last Test Date. If there is no testing during the final exam period, at most one assignment should fall due between May 12 and the end of the last regularly scheduled class"

THe pdf of HW7 has been updated -- the lines about the cities in Sweden has been removed. The rest is the same. The MDS lecture notes are on stellar.

Announced on 10 May 2017  9:30  p.m. by Raj Rao Nadakuditi

HW 7 posted on Gradescope and Stellar (due May 20th -- no extension!)

See under Stellar and Gradescope. Zip file on Stellar for MDS problem.

Enjoy!

Announced on 30 April 2017  6:30  p.m. by Raj Rao Nadakuditi

Independent Component Analysis notebook under Materials

See under Materials section.

Additional reading is posted on Stellar too.

Announced on 27 April 2017  10:33  p.m. by Raj Rao Nadakuditi

HW 6 (due April 29th) posted under materials and Gradescope (not on Piazza)

See under materials section. HW 6 is due by midnight on Saturday, April 29th. We recommend you start early :) We'll assign HW 7 on April 30th and it will be due May 20th -- that will be the last homework assigned for the class :)

The files needed for HW6 can be downloaded at

https://www.dropbox.com/sh/of2hxs4wa78ieav/AADGvfLhVGmczKHFZraj4dxEa?dl=0

Mandatory for both 18.065 and 18.0651

1, 2, 3, 4 (except 4-a) 6, 7 , 12b, 13b

Optional/bonus questios for 18.065

4-(a), 5, 7 c, 7 d, 8, 9, 10, 11, 12a, 13a,

Optional/bonus questions for 18.0651

5, 9, 11

In this homework set, you will see why recognizing and exploiting Fourier transforms in data can help speedup the algorithm dramatically, how to remove graffiti from images and how to denoise an image using the L1 norm (or its surrogate via a 'potential function')

Announced on 10 April 2017  8:01  p.m. by Raj Rao Nadakuditi

Procrustes analysis, the Quadratic assignment problem & decrypting substituion ciphers

The lecture notes on the Procrustes problem have been posted on Stellar (under materials).

See https://math.uchicago.edu/~shmuel/Network-course-readings/MCMCRev.pdf

for a fascinating real-world example of a "matrix method" used to decrpyt a substitution cipher.

At the heart of the above paper is the quadratic assignment problem (QAP) which involves finding the permutation matrix that maximizes

Trace(PAP'B)

where the "A" matrix is the so-called "1-gram probability matrix" of English inferred from data (by parsing, say, War & Peace or the Bible) and the "B" matrix is the equivalent 1-gram probability matrix for the ciphered test.

The paper
https://arxiv.org/pdf/0902.1843.pdf
highlights the connection between the famous Travelling Salesman Problem and the QAP. The solution proposed involves circulant matrices!

And finally, here is a great article about modern approaches to the travelling salesman problem

https://www.quantamagazine.org/20130129-computer-scientists-take-road-less-traveled/

Bonus points for implementing the algorithm in Persi Diaconis' paper and making a notebook that works!

Announced on 04 April 2017  8:34  p.m. by Raj Rao Nadakuditi