1 LINEAR ALGEBRA PROJECT Problem1: Image Classi cation 1. Download the handwritten digits dataset. Dataset is given as a MATLAB struct with name "data". data.train 8 is the set of images of digit "8", data.train 1 is the set of images of digit "1", data.test is a set of mixed images of digits "1" and "8", and data.labels is the array of labels for samples in data.test. (Label is an integer to categorize the samples (images). Labels of images of digit "8" are 8, labels of images of digit "1" are 1.) 2. "data.train 8" and "data.train 1" are matrices of size [200,256], and "data.test" is a matrix of size [1147, 256]. Each row of these three matrices represents an image of size [16,16] which is reshaped to be an array of size [1,256]. Hence, in data.train 8 and data.train 1 rows represent samples (images), and columns represent pixel intensity values. Each of "data.train 8" and "data.train 1" store 200 images, while "data.test" store 1147 images. 3. Perform the following steps for both data.train 8 and data.train 1: (a) Generate a for loop to visualize all samples from the given dataset. Since all samples are stored as array, you should convert each sample array to an image of size [16,16]. MATLAB HINT: In order to convert arrays to images you can use "reshape" command, and to visualize images you can use "imshow" command. (b) You now have overall idea about your dataset. Now you will nd a basis for the given dataset. What do you expect of elements of basis to be? What is the size of each element in basis of these images? (c) Calculate the Singular Value Decomposition (SVD) of the given dataset. What are the sizes of the resulting matrices U, S and V? Interpret the matrices S and V. MATLAB HINT: you can use "svd" command. (d) Find a basis for the row space of the given dataset by using SVD de- composition. What information about the given dataset do you get from the basis of rowspace? (e) Convert basis elements to matrices of size [16,16] and generate a for loop to visualize them. Sort the basis elements from most informative to least informative. How do you decide that order (Relate with matrix S.)? Now visualize elements. What do you observe about the order of the basis elements. (f) Store the most informative 3 basis elements. These 3 elements will give the "best 3-rank approximation". 4. You have 3 most informative basis elements for each of classes (3 basis ele- ments for data.train 8 and 3 basis elements for data.train 1). Now you will generate a decision strategy to predict label of samples in data.test. Since 3 basis elements can not form a complete basis for any of the given ma- trices, the representation of samples with these 3 basis elements may not give the exact representation but it will give an approximation. Because of the same reason these representations will not be unique. So you can nd multiple representations for each sample. As a reconstruction choose the one which gives the minimum error when it is compared to the sample itself. This representation is called as the minimum error representation (or best k-rank approximation). Check the reference tutorial for "best k-rank approximation" and error calculation of approximations. 5. Create empty arrays as error 8, error 1 and reconstruction errors with size [1147,1]. 6. For each samples in the data.test, nd minimum error representation by using 3 basis elements of data.train 8. Store the error in error 8. 7. For each samples in the data.test, nd minimum error representation by using 3 basis elements of data.train 1. Store the error in error 1. 8. Compare the calculated errors for each sample and set the label of the sample with the digit (8 or 1) whose basis elements give the minimum error. (If error 8 error 1 set label as 1, if error 1 error 8 set label as 8). Store the labels of samples in a column vector labels val (clearly labels val will be in size [1147,1]). 9. Now you will ll the empty array reconstruction errors by using correct labels: Set reconstruction errors 3(i) = error 8(i) if data.labels(i)=8, reconstruction errors 3(i) = error 1(i) if data.labels(i)=1: 10. Calculate the overall classi cation accuracy as accuracy 3 = number of correctly labeled samples total number of test samples 11. Repeat the listed steps in 3 to nd the most informative 2 basis elements and 1 basis element. Store the accuracy matrices as accuracy 2 and accuracy 1, and reconstruction error matrices as reconstruction errors 2 and reconstruc- tion errors 1 respectively. Compare the three classi cation accuracies by plotting a bar plot. Compare three average reconstruction errors by plot- ting a bar plot. How does the classi cation accuracy change when number of used basis elements are changed? How does the averaged reconstruction error changes? How do you interpret relation between reconstruction error and classi cation accuracy? Is there a direct relation between them? 12. Give possible strategies to improve the classi cation accuracy.

In project folder there is one Matlab struct "data" which contains data.train_8 is a matrix with 200 rows, and each row is a vector of size [1,256]. Each row is vectorized form of an image of size [16,16] three matrices and one array: data.train 1 is a matrix with 200 rows, and each row is a vector of And that image is image of digit 8. Example size [1,256]. Each row is vectorized form of an image of size [16,16] And that image is image of digit 1. Example In project folder there is one Matlab struct "data" which contains data.train_8 is a matrix with 200 rows, and each row is a vector of size [1,256]. Each row is vectorized form of an image of size [16,16] three matrices and one array: data.train 1 is a matrix with 200 rows, and each row is a vector of And that image is image of digit 8. Example size [1,256]. Each row is vectorized form of an image of size [16,16] And that image is image of digit 1. Example