AI61003 Assignment 1 Solution

1. Let Pn(R) denote the set of all polynomials in indeterminate x with real coefficients.
(a) Prove that Pn(R) is a real vector space.
(b) Define a function F : Pn(R) → R as
In other words, the function assigns every polynomial with the value of its derivative at x = 0. Prove that this is a linear functional.
(c) Find an inner product representation for the linear functional in the abovequestion.
2. Let x ∈ Rn and 1n be the n-vector with all entries 1. Let avg(x) and std(x) be as defined in the class. Then for any α,β ∈ R prove the following.
(a) avg(αx + β1n) = αavg(x) + β
(b) std(αx + β1n) = |α|std(x)
3. Let w ∈ Rn be a given vector with wi > 0 for i = 1,2,...,n. Then for any x ∈ Rn, define the function

Show that the function ∥ · ∥w defines a norm called as weighted norm.
4. Discuss in details the existence and uniqueness conditions for system of linearequations where Ax = b where A ∈ Rm×n and b ∈ Rm are given matrices.
5. Prove that matrix multiplication is associative; however matrix multiplicationis not commutative. Further, let A ∈ Rp×q,B ∈ Rq×r,C ∈ Rr×t be given matrices. Derive conditions on p,q,r,t such that (AB)C is computationally more efficient than A(BC).
6. Define left inverse of a matrix A. Determine in which of the following cases left inverse exists. In each of the following cases, is it possible to characterize all the left inverses if one left inverse exists.
1
0 (a) A = 0
 
1
0
2 0 
(b) A = 0 −2
3 3
7. Let A ∈ Rn×n be an invertible matrix. Construct the matrices Lij discussed in the class and write down the procedure to compute LU decomposition of A.
8. Consider k-means clustering algorithm as follows with the standard terminology and notation introduced in the class as follows.
Input: x1,x2,...,xN ∈ Rn. Initial list of k cluster representatives z1,...,zk.
Output: Cluster assignment c1,c2,...,cN
Repeat until convergence
1. Cluster assignment based on cluster representatives.
2. Update cluster representatives.
(a) In Step 1, what is the computational complexity?(b) In Step 2, what is the computational complexity?
(c) Assuming 10 iterations are performed, how many number of computations are involved to obtain the cluster assignment for the given data points?
9. Image Clustering: Consider the MNIST database of handwritten digits. Choose 100 images of each digit from this data set. In the notation of Problem 8Item.15, determine values N and n. Fix a reasonable convergence criterion.
Perform the following exercises (a),(b) and (c) in two cases: case (i) random initialization of cluster representatives; case(ii) choose cluster representatives from the given data set.
(a) For k = 20, run the above algorithm to cluster the given images into 20 clusters. Plot the cluster representatives after the algorithm converges. Count the number of iterations.
(b) Choose 50 images (not chosen previously) from the MNIST data set randomly and assign the clusters to these test images. What is the accuracy of cluster assignment?
Does the choice of initial condition have any effect on the performance of k-means clustering algorithm?
10. Document Clustering: Collect the set of documents form Wikipedia with the following titles:
Linear algebra
Data Science
Artificial intelligence
European Central Bank
Financial technology
International Monetary Fund
Basketball Swimming
Cricket
Vectorize the documents with TF-IDF vectorizer (Word Frequency Vectors) and perform the following operations.
(a) Apply k-means clustering on the vectorized data for k = 4,k = 8andk =
12.
(b) Find the document-cluster association (Which document belongs to whichcluster) for each k in the above clustering.
(c) Out of the three k values which one is better for the given data and why?
Link for tutorial video for this problem: https://www.youtube.com/watch?v=YcaMlHtBdp4
****************** THE END ******************