AI61003- Assignment 2: Linear Algebra for AI and ML Solved

ANSWER ALL THE QUESTIONS
Let A,B ∈ Rn×n. Prove that ∥AB∥2 ⩽ ∥A∥2∥B∥2. This property of 2-norm is called as sub-multiplicativity property. Does this property hold true for Frobenius norm?
Let A ∈ Rn×n be an invertible matrix. Define maxmag(A) and minmag(A) and cond(A). Show that
1

maxmag(A) = minmag(A−1)
maxmag(A)

cond(A) = minmag(A)
In each of the following cases, consider the matrix A ∈ Rm×n as a linear function from Rn to Rm. Plot the unit sphere in Rn. Plot the ellipsoid obtained in Rm as image of the unit sphere in Rn. Compute the condition number of A (using inbuilt command). Further, if m = n, check whether the matrix is invertible. Compute the determinant of A as well. Is there any relationship between determinant and condition number?
, where ε = 10,5,1,10−1,10−2,10−4,0.

For a matrix A with the property that the columns of A are linearly independent, give the geometrical interpretation of the least squares solution to the problem Ax = b and justify the name normal equations. In case, the matrix A does not have linearly independent columns, comment on the nature of the least squares solution.
Consider the system of linear equations Ax = b where A ∈ Rn×n is an invertible matrix and b ∈ Rn is a given vector. Discuss the advantages in the case when A is orthogonal.
Bi-linear interpolation: We are given scalar value at each of the MN grid points of a grid in R2 with a typical grid point represented as Pij = (xi,yj) where i = 1,2,...,M and j = 1,2,...,N and x1 < x2 < ·· < xM and y1 < y2 < ··· < yN. Let the scalar value at the grid point Pij be referred to as Fij for i = 1,2,...,M and j = 1,2,...,N. A bi-linear interpolation is a function of the form
f(u,v) = θ1 + θ2u + θ3v + θ4uv

where θ1,θ2,θ3,θ4 are the coefficients. This function further satisfies f(Pij) = Fij for i = 1,2,...,M and j = 1,2,...,N.

Express these interpolation conditions as a system linear equations of theform Aθ = b where b is an MN vector consisting of Fij  Write clearly all the entries of A, θ and b and their sizes.
What are the minimum values of M and N so that you may expect a unique solution to the system of equations Aθ = b?
Iterative LS: Let A ∈ Rm×n have linearly independent columns and let b ∈ Rm be a given vector. Further, let x denote the LS solution to the problem Ax = b. b
Define x(1) = 0 and for k = 0,1,2,...

Show that the sequence {x(k)} converges to x as k → ∞. b
Discuss the computational complexity of computing {x(k)} for any k ⩾
Generate a 30 × 10 random matrix A and a 30 × 1 random vector b. Check that the matrix is full column rank! Run the algorithm for 100 steps. Verify numerically that the algorithm converges to x.
b (d) Do you think this iterative method may be computationally beneficial over the direct methods of computing the LS solution?

Suppose that z1,z2,...,z100 is observed time series data. An autoregressive model for this data has the following form.
zt+1 = θ1zt + ··· + θMzt−M+1, t = M,M + 1,...,100 b

where M is the memory or the lag of the model. This model can be used to predict the next observation in the time series.

Set up a least squares problem to estimate the parameters in the model.(b) Clearly write down the matrices A and b in the least squares formulation.
What is the special structure that one can observe in A?
Is there any relation of rank of A with M?
Polynomial Classifier: Generate 500 random vectors x(i) ∈ R2 for i = 1,2,...,500 from a standard normal distribution. Define, for i = 1,2,...,500,
                                                                    1     otherwise

Fit a polynomial least squares classifier of degree 2 to the data set using the polynomial

Give the error rate of the classifier using the confusion matrix.
Show the regions in the R2 plane where the classifier model ) = 1 and
Does the second degree polynomial g = x1x2 classify the generated points with zero error? Compare the parameters estimated polynomial model from the data with those of g.
MNIST dataset: For each of the digit 0,1,...,9 randomly select 1000 images to generate a training data set of size 10000 images. Similarly generate a test data set of 1000 images as a test data set. Fit a linear least squares classifier to classify the data set into 10 classes and test prediction accuracy of the model using the 10×10 confusion matrix. Do not use any inbuit functions for fitting the model.