Competency
In this project, you will demonstrate your mastery of the following competencies:
- Interpret the properties of vector spaces
- Utilize advanced matrix techniques to solve complex linear problems
Scenario
You are employed as a computer programmer for a popular social media
site that stores a large amount of user media files. You believe you
have found a way to reduce costs by compressing image files using
singular-value decomposition (SVD). The compressed files would require
less storage space, which would result in savings for the company. You
think it will work, but you want to test your theory and record the
steps you take to use as a reference when sharing your idea with
management.
Directions
In order to guarantee that management fully understands the process,
you have mapped out the following steps to ensure you have captured the
process and have data to support your findings and to share with
management. Your plan is to demonstrate computations on a simple 3 x 3
matrix where the computations are easier to follow. Then you will
perform similar computations on a large image to compress the image data
without significantly degrading image quality.
To develop your idea proposal, work the problems described below. As
you complete each part, make sure to show your work and carefully
describe how you arrive at your final answer. Any MATLAB code or MATLAB
terminal outputs you generate should be included in your idea proposal
to support your answers and work.
MAT 350 Project Two SVD and Image Compression Overview SVD and Image Compression Overview Consider the matrix with entries represented by “one-byte” integers. One byte equals 8 bits of information, so each value in the matrix is represented by an integer in the range from 0 to 255. Since each matrix entry requires one byte of storage, the total matrix requires bytes of storage space. The singular value decomposition (SVD) can be used to compute an orthogonal decomposition of a matrix. Given the matrix , the SVD can be used to decompose the matrix as , where is an orthogonal matrix, is an orthogonal matrix, and is a rectangular diagonal matrix whose diagonal contains the singular values of . This representation is very similar to the eigenvalue diagonalization (called eigendecomposition) already studied in the course. However, a primary difference between SVD and eigendecomposition is that SVD can be used for rectangular matrices, while eigendecomposition can be used only on square matrices. SVD can be used to construct a low-rank approximation of the original matrix. If only the first singular values are used, then can be approximated by the matrix defined as: where is a matrix containing the first columns of , is a matrix containing the first rows and columns of , and is a matrix containing the first columns of . Observe that this approximation essentially throws away all of the information stored in the dimensions and higher. After computing the image approximation, we must be careful to make sure that the approximation has the correct data format. Each value in the matrix must be an unsigned 8-bit integer data type. Since the approximation now likely has real-valued quantities in it, we will round these entries to the closest integer and then cast the data type to an integer. This allows the image to be properly displayed in software programs such as MATLAB. So, after computing , we’ll typically execute a command similar to the following: Ak = uint8(round(Ak)) The matrix has a total of entries that must be stored. Since is a diagonal matrix, only its diagonal elements need to be stored. The matrix has entries that must be stored. Thus, the total number of values to store for the low-rank matrix is . Compared to the original storage requirement of , using only singular values to approximate with achieves a compression ratio of To provide a specific example, if , , and , this would result in a compression ratio of While the low-rank approximation can require significantly less storage space than the original matrix, it is an approximation that in general is not equal to the original matrix. To quantify the error between and , we can compute the root mean square error as: The matrix norm above is the Frobenius norm, which is defined as the square root of the sum of absolute squares of its elements. In general, the RMSE will increase as the value for decreases, i.e., the less storage used, the larger the approximation and the larger the error. This tradeoff between compression and error will be investigated graphically in the project. Additional Useful MATLAB Commands MATLAB can compute the singular value decomposition (SVD) of a matrix using the svd() function. The outputs of the svd() function are the three matrices comprising the SVD decomposition. The MATLAB command is: [U,S,V] = svd(A); To display an image in MATLAB, you first need to load the file into the workspace. There are several ways to do this, but one option is the load command. To display an image in MATLAB, an empty figure must first be initialized. The MATLAB command is: figure; This command initializes an empty figure. The next command that plots or displays information will appear in the figure. The MATLAB command imshow() can be used to display an image in a figure. If the image is stored in matrix , the image can be displayed with the command: imshow(A); The MATLAB command title() can be used to title a figure. The argument of the title() function is a string with the desired title, e.g., title(‘My Image Title’) Files can be easily uploaded to or downloaded from the MATLAB Online interface. Under the Home tab, there are Upload and Download buttons. Clicking the Upload button will prompt the user to select the file to upload. If a single file is selected (e.g., project01Solution.pdf), the Download button can be clicked to download the file to the user’s local computer. Figure: A folder in MATLAB with the project01Solution.pdf file selected 3 Firefox File Edit View History Bookmarks Tools Window Help rm STORE 0 vc oc | wx © SY QO 8 #2 https/flearn.snhu.edu/d2l/le/content/1158805/viewContent/20334144 View 9 4 £3 Most Visited @) Import to Loox [Bll RE my license (@) App Store | Apporto, [NTIS To develop your idea proposal, work the problems described below. As you complete each part, make sure to show your work and carefully describe how you arrive at your final answer. Any MATLAB code or MATLAB terminal outputs you generate should be included in your idea proposal to support your answers and work. 2 A= 5 8 Use the svd() function in MATLAB to compute A1, the rank-1 approximation of A. Clearly state what A1 is, rounded to 4 decimal places. Also, compute the root mean square error (RMSE) between A and Ax. 2. Use the svd() function in MATLAB to compute Az, the rank-2 approximation of A. Clearly state what Az is, rounded to 4 decimal places. Also, compute the root mean square error (RMSE) between A and A2. Which approximation is better, A1 or A? Explain. 3.For the 3 x 3matrix A, the singular value decomposition is A = USV’ where U = [u; uz us] Use MATLAB to compute the dot product di = dot(us, uz), Also, use MATLAB to compute the cross product ¢ = cross(u1. uz)and dot product d2 = dot(€, us). Clearly state the values for each of these computations. Do these values make sense? Explain. 4. Using the matrixU = [u1 u2 us], determine whether or not the columns of r span R3. Explain your approach. 5. Use the MATLAB imshow() function to load and display the image A stored in the provided MATLAB image.mat file (available in the Supporting Materials area). For the loaded image, derive the value of k that will result in a compression ratio of CR = 2. For this value of k, construct the rank-k approximation of the image. 6. Display the image and compute the root mean square error (RMSE) between the approximation and the original image. Make sure to include a copy of the approximate image in your report. 7.Repeat steps 5 and 6 for CR ~ 10, CR ~ 25, and CR ~ 75. Explain what trends you observe in the image approximation as cr increases and provide your recommendation for the best cr based on your observations. Make sure to include a copy of the approximate images in your 1. Consider the matrix: 3 x 3: 12 3 4 6 7