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...
-
Refer to Figure 15.52. Using Taylor's stability chart (Figure 15.21), determine the factor of safety, Fs, against sliding for the slopes with the following characteristics: Slope: 2.5H: 1V, ( = 18.8...
-
Staff are encouraged to apply social work values in practice. Rank the statements on a scale of 1 to 10 where 1 is never true and 10 is always true for an organisation you work in or are associated...
-
True or false: Ensemble models using voting or propensity averaging do not perform well with misclassification costs.
-
Planning is one of the most demanding and important aspects of an audit. A carefully planned audit increases auditor efficiency and provides greater assurance that the audit team addresses the...
-
Fit Fanatic Company is a manufacturer of commercial grade exercise bikes that are sold to hotels and health clubs. Maintaining the bikes is an important area of customer satisfaction. Because of...
-
Determine (a) The equivalent resistance of the circuit shown in fig. 19-39, and (b) The voltage across each resistor. 680 2 470 2 820 2 12.0 V
-
Identify which of the following items are not included as part of general-purpose financial statements but are part of financial reporting. a Revenue forecasts b. Statement of cash flows c. Press...
-
Implement the nearest neighbor algorithm in the programming language of your choice. The algorithm should work with vectors of up to 10 integer values and allow up to 10 integer classifications. By...
-
Use the operators described in Section 16.2.4 and the STRIPS method to solve the block world planning problem shown in Figure 16.11. The first state shown is the start state and the second state is...
-
Implement a Bayesian belief network in the programming language of your choice to represent a subject in which you are interested (for example, you might use it to diagnose medical conditions from...
-
Researchers have measured the acceleration of racing greyhounds as a function of their speed; a simplified version of their results is shown in Figure P4.67. The acceleration at low speeds is...
-
If the rate at which energy is dissipated by resistor 1 in Figure P31.86 is \(2.5 \mathrm{~W}\), and \(R_{1}=10 \Omega, \mathscr{E}_{1}=12 \mathrm{~V}\), and \(\mathscr{E}_{2}=6 \mathrm{~V},\) (a)...
-
Brooks Company carries three inventory items. The following information pertains to the ending inventory iten A Quantity 210 245 171 Unit Cost $10 12 6 Unit Market value 59 11 0 K Required o....
-
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...
-
Identify two constraints in accounting. AppendixLO1
-
A medium-sized UK-based insurance company underwrites mainly commercial and industrial property and motor and liability insurance. Outline, with reasons, the types of reinsurance it is likely to buy...
-
If the present value of $1.00 received N years from today at an interest rate of int% is 0.270, what is the future value of $1.00 invested today at an interest rate of int% for N years? a. $1.00 b....
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App