In the real world, it is not computationally practical to directly solve for the eigenbasis for...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
In the real world, it is not computationally practical to directly solve for the eigenbasis for large matrices as you might do for small matrices on paper. You need to build an algorithm that sequentially computes the eigenbasis for a square symmetric matrix Q = ATA (Note: Any matrix that can be written with A € RNXN in this form is symmetric). To accomplish this we are given access to a function, (V₁, 2₁) = f(Q), that returns the largest eigenvalue of the matrix Q and the corresponding eigenvector. We will use this function to build a sequential greedy algorithm (similar to Orthogonal Matching Pursuit) that computes the eigenvectors and eigenvalues in descending order. IMPORTANT: Throughout the problem, you should assume that the magnitude of each eigenvector is 1 (i.e. ||||= 1), that the eigenvalues are real, unique, and distinct, and that A₁ > A₂ >> AN > 0. (a) Show that the matrix Q = AT A is symmetric (i.e. Q =Q) when, A = 12 3 (2) (b) Given two distinct eigenvalue/eigenvector pairs, (2.) and (2.ve). show that for the symmetric matrix Q = A' A, if λ Athen (v.) = 0 (i.e. any pair of eigenvectors with distinct eigenvalues is orthogonal). Hint: Consider: QUk = 2³k V/Q=dev. (c) Let us consider V to be an orthonormal matrix, where -44-9 (3) (5) Show that if V is an orthonormal matrix, then VTV = I. (d) Recall that the columns of orthonormal matrix V form a basis for RN, as you proved in the discussion sections. Assume a= [a₁... a represents in the basis of V. Find (v,,.). VN. Hint: Write x as a linear combination of the column vectors V₁, (e) Let us define, V(2) +4 Assume a = [a₁...an] represents in the basis of V. Find , the projection of a vectorERN onto the columns of the orthonormal matrix V(2): (6) =projcl(v(²) (*). What is the magnitude of the error vector, î-x? (f) We know that because Q is symmetric, V is an orthonormal matrix. We use the idea of diagonalization and part (c) of the problem to express Q as: Q=A'A=VAV¹ = VAVT = [₁ A= 20 0 0 2₂ 0 0 023 : 0 0 0 *** 0 0 0 AN (8) (9) Let Q2Q-A₁₁. Thus, Q(2) represents Q after the component associated with direction v₁ is removed. Show that is in the null space of Q(2). Hint: Can you write Q(2) using Eq. (8)? (g) Recall the function that returns the largest eigenvalue and corresponding eigenvector of a matrix, (7) (F₁,2₁) = S(Q). (10) Design a sequential greedy algorithm that returns a list of eigenvalues of matrix Q in descending order of values. You may assume that all the eigenvalues of Q are positive (>0). You are allowed to use the function defined in Eq. (10) that returns the largest eigenvalue and corresponding eigenvector and what you know from part (f). In the real world, it is not computationally practical to directly solve for the eigenbasis for large matrices as you might do for small matrices on paper. You need to build an algorithm that sequentially computes the eigenbasis for a square symmetric matrix Q = ATA (Note: Any matrix that can be written with A € RNXN in this form is symmetric). To accomplish this we are given access to a function, (V₁, 2₁) = f(Q), that returns the largest eigenvalue of the matrix Q and the corresponding eigenvector. We will use this function to build a sequential greedy algorithm (similar to Orthogonal Matching Pursuit) that computes the eigenvectors and eigenvalues in descending order. IMPORTANT: Throughout the problem, you should assume that the magnitude of each eigenvector is 1 (i.e. ||||= 1), that the eigenvalues are real, unique, and distinct, and that A₁ > A₂ >> AN > 0. (a) Show that the matrix Q = AT A is symmetric (i.e. Q =Q) when, A = 12 3 (2) (b) Given two distinct eigenvalue/eigenvector pairs, (2.) and (2.ve). show that for the symmetric matrix Q = A' A, if λ Athen (v.) = 0 (i.e. any pair of eigenvectors with distinct eigenvalues is orthogonal). Hint: Consider: QUk = 2³k V/Q=dev. (c) Let us consider V to be an orthonormal matrix, where -44-9 (3) (5) Show that if V is an orthonormal matrix, then VTV = I. (d) Recall that the columns of orthonormal matrix V form a basis for RN, as you proved in the discussion sections. Assume a= [a₁... a represents in the basis of V. Find (v,,.). VN. Hint: Write x as a linear combination of the column vectors V₁, (e) Let us define, V(2) +4 Assume a = [a₁...an] represents in the basis of V. Find , the projection of a vectorERN onto the columns of the orthonormal matrix V(2): (6) =projcl(v(²) (*). What is the magnitude of the error vector, î-x? (f) We know that because Q is symmetric, V is an orthonormal matrix. We use the idea of diagonalization and part (c) of the problem to express Q as: Q=A'A=VAV¹ = VAVT = [₁ A= 20 0 0 2₂ 0 0 023 : 0 0 0 *** 0 0 0 AN (8) (9) Let Q2Q-A₁₁. Thus, Q(2) represents Q after the component associated with direction v₁ is removed. Show that is in the null space of Q(2). Hint: Can you write Q(2) using Eq. (8)? (g) Recall the function that returns the largest eigenvalue and corresponding eigenvector of a matrix, (7) (F₁,2₁) = S(Q). (10) Design a sequential greedy algorithm that returns a list of eigenvalues of matrix Q in descending order of values. You may assume that all the eigenvalues of Q are positive (>0). You are allowed to use the function defined in Eq. (10) that returns the largest eigenvalue and corresponding eigenvector and what you know from part (f).
Expert Answer:
Related Book For
Understandable Statistics Concepts And Methods
ISBN: 9780618986927
9th Edition
Authors: Charles Henry Brase, Corrinne Pellillo Brase
Posted Date:
Students also viewed these mathematics questions
-
Write a note on immigration-related issues in the real world by focusing on the United States.
-
DECISION ANALYSIS PROJECT: MODELING IN THE REAL WORLD This assignment is an individual project-based assignment with the objective is to design a quantitative analysis approach according to the...
-
Suppose in the real world you observe that black basketball players get paid more than white basketball players. Do you conclude that discrimination is present? Explain why or why not.
-
An array is bitonic if it consists of an increasing sequence of keys followed immediately by a decreasing sequence of keys. Given a bitonic array, design a logarithmic algorithm to find the index of...
-
Assume the facts in Question 3. You begin to consider the labor force that the joint venture will need. Ayantuga suggests that the venture technicians should make regular technical training visits to...
-
Research a new technology and discuss at least two pros and two cons of implementing it in an emergency management or homeland security focused organization. Be sure to identify the organization you...
-
P 83 Use the Standard Normal Table or technology to find the z-score that corresponds to the cumulative area or percentile. Table 4-Standard Normal Distribution Arca Z 0 Z .09 .08 .07 .06 .05 .04 .03...
-
For diagrams (a)-(d), compute the unknown values: B, C, V, x, respectively, using the minimum number of compound interest factors. 200 200 200 200 100 100 100 -:- -2-3- -4 -2-3-4- i- 10% i= 10% (h)...
-
Choose one of the four basic leader behavior styles suggested by Hersey and Blanchard. Discuss the specifics of the task and relationship behaviors of the chosen style. Provide a realistic example of...
-
Decor and More Imports recently reported the following stockholders' equity: ai (Click the icon to view the data.) Suppose Decor and More split its common stock 2-for-1 in order to decrease the...
-
When discussing imagination, Seeling had three points. Which one of these was NOT one of these points? https://www.youtube.com/watch? time_continue=967&v=CgCdsERkqrc&feature=emb _logo Question has 4...
-
What is the difference between a stack and a queue data structure?
-
Social skill is important in the service industry. As a future tourism and hospitality professional, how are you going to improve your social skills? Another key component of emotional intelligence...
-
Imperial Jewelers manufactures and sells a gold bracelet for $404.00. The company's accounting system says that the unit product cost for this bracelet is $267.00 as shown below: Direct materials...
-
You will create a cost function for this exercise using your birthday. Make note of your birthday using the number of the month (1-12) and the number for the day of the month (1-31) below. Month (m):...
-
Pre-requisite: Postman Account 1. Create New Collection (2) a. Collection Name should be {Student1FirstName}-{Student2FirstName}-Assignment6 b. Enter Collection Description C. Collection Variable:...
-
On December 31, 2020, the entire inventory of Naren Corp. was destroyed by a flood. Sales and purchases for the year had been $2.6 million and $1.2 million, respectively. The beginning inventory...
-
The Adjusted Trial Balance columns of a 10-column work sheet for Webber Co. follow. Complete the work sheet by extending the account balances into the appropriate financial statement columns and by...
-
Consider the information given in Figure 4-12, Vulnerable Knees. What is the probability that an orthopedic case selected at random involves knee problems? Of those cases, estimate the probability...
-
Discuss each of the following topics in class or review the topics on your own. Then write a brief but complete essay in which you summarize the main points. Please include formulas and graphs as...
-
Garrison Bay is a small bay in Washington state. A popular recreational activity in the bay is clam digging. For several years, this harvest has been monitored and the size distribution of clams...
-
One of the main fears that retail startups have is if they will be able to compete against Walmart, Home Depot, and the other big-box stores. This is a legitimate fear. Big-box stores continue to...
-
Influencer marketing is a type of marketing where companies partner with influencers, who have a significant following on social media platforms, to promote their products or services. Influencers...
-
In the summer of 2015, Stephen Kuhl and Kabeer Chopra made their way to Philadelphia to prepare for business school. It was their first semester in the Wharton MBA program. They were both in an...
Study smarter with the SolutionInn App