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 449 (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 Q2QA₁₁. 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 449 (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 Q2QA₁₁. 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 immigrationrelated issues in the real world by focusing on the United States.

DECISION ANALYSIS PROJECT: MODELING IN THE REAL WORLD This assignment is an individual projectbased 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...

Megaton Corp., an electric guitar retailer, was organized by Bonita Eaves, Helen Brock, and Freida Sager. The charter authorized 400,000 shares of common stock with a par of $10. The following...

_____________ are interested in demonstrating concern for others emotions and interests, finding common ground, and responding.

A chain drive is used for: (a) Short distance (b) Medium distance (c) Long distance (d) Distance is no barrier

On October 15, 2020, the board of directors of Ensor Materials Corporation approved a stock option plan for key executives. On January 1, 2021, 20 million stock options were granted, exercisable for...

Magic Mountain retires its 9% bonds for $128,000 before their scheduled maturity. At the time, the bonds have a face value of 126,000 and a carrying value of $117,000. Record the early retirement of...

Laval produces lighting fixtures. Budgeted Information for Its two production departments follows. The departments use machine hours (MH) and direct labor hours (DLH). Overhead cost Direct labor...

A construction company is considering a project with a total estimated cost of $10,000,000. The project is expected to take 2 years to complete. The company's risk manager estimates that there is a...

An investment has a 30% chance of producing a 15% return, a 40% chance of producing a 20% return, and a 30% chance of producing a 10% return. Part (A): What is its expected return? Part (B): What is...

Despite lots of attention, money, and effort, performance appraisals remain an area with which few managers or employees are satisfied. Explain some of the reasons for this dissatisfaction (i.e.,...

Operations of different companies differ in regards to four Vs in operations. Discuss the concepts clearly bringing out the differences in operations function of companies.

In 1995, a given Japanese imported automobile sold for 1,650,000 yen, or $8,400. If the car still sold for the same amount of yen today but the current exchange rate is 115 yen per dollar, what would...

what decision refers to the selection of the best means to achieve a goal and not to the selection of the goal itself. If an individual wishes to own a car primarily as a means of transportation,...

Hyde Catering Inc. is a caterer of corporate lunches and events. The following is Hyde's sales forecast by quarter for the upcoming year. Hyde Catering Inc. Forecasted Sales For the Year Ended...

Compile data on consumption and expenditures for the following categories in 30 different countries: (1) food and beverages, (2) clothing and footwear, (3) housing and home operations, (4) household...

Consider the information given in Figure 412, 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...

A company issues $1,000,000 face value of 10year bonds on January 1, 2015 when the market interest rate on bonds of comparable risk and terms is 5%. Th e bonds pay 6% interest annually on December...

Midland Brands issues threeyear bonds dated January 1, 2015 with a face value of $5,000,000. Th e market interest rate on bonds of comparable risk and term is 3%. If the bonds pay 2.5% annually on...

A company redeems \($1\),000,000 face value bonds with a carrying value of \($990\),000. If the call price is 104 the company will: A . reduce bonds payable by \($1\),000,000. B . recognize a loss on...
Study smarter with the SolutionInn App