Computing the standard inner product between two vectors a, b R n requires n multiplications and
Question:
Computing the standard inner product between two vectors a, b ∈ Rn requires n multiplications and additions. When the dimension n is huge (say, e.g., of the order of 1012, or larger), even computing a simple inner product can be computationally prohibitive.
Transcribed Image Text:
Let us define a random vector r ER" constructed as follows: choose uniformly at random an index i = {1,...,n}, and set r; = 1, and r;= 0 for ji. Consider the two scalar random numbers a, b that represent the "random projections" of the original vectors a, b along r: Prove that ã = r¹a = a₁, b = r¹b = b₁. nE{ab} = a¹b, that is, nāb is an unbiased estimator of the value of the inner product ab. Observe that computing não requires very little effort, since it is just equal to najb;, where i is the randomly chosen index. Notice, however, that the variance of such an estimator can be large, as it is given by ¹ [a²b² - (a + b)² k=1 var{nab}= (prove also this latter formula). Hint: let e; denote the i-th standard basis vector of R"; the random vector r has discrete probability distri- bution Prob{r = e;} = 1/n, i = 1,...,n, hence E{r} = 11. Further, observe that the products rr¡ are equal to zero for k ‡ j and that the vector r² = [...] has the same distribution as r. Generalizations of this idea to random projections onto k-dimen- sional subspaces are indeed applied for matrix-product approxima- tion, SVD factorization, and PCA on huge-scale problems. The key theoretical tool underlying these results is known as the Johnson- Lindenstrauss lemma.
Fantastic news! We've Found the answer you've been seeking!
Step by Step Answer:
Answer rating: 75% (4 reviews)
Indeed when dealing with highdimensional vectors in Rn the computational cost of computing the stand...View the full answer
Answered By
JAPHETH KOGEI
Hi there. I'm here to assist you to score the highest marks on your assignments and homework. My areas of specialisation are:
Auditing, Financial Accounting, Macroeconomics, Monetary-economics, Business-administration, Advanced-accounting, Corporate Finance, Professional-accounting-ethics, Corporate governance, Financial-risk-analysis, Financial-budgeting, Corporate-social-responsibility, Statistics, Business management, logic, Critical thinking,
So, I look forward to helping you solve your academic problem.
I enjoy teaching and tutoring university and high school students. During my free time, I also read books on motivation, leadership, comedy, emotional intelligence, critical thinking, nature, human nature, innovation, persuasion, performance, negotiations, goals, power, time management, wealth, debates, sales, and finance. Additionally, I am a panellist on an FM radio program on Sunday mornings where we discuss current affairs.
I travel three times a year either to the USA, Europe and around Africa.
As a university student in the USA, I enjoyed interacting with people from different cultures and ethnic groups. Together with friends, we travelled widely in the USA and in Europe (UK, France, Denmark, Germany, Turkey, etc).
So, I look forward to tutoring you. I believe that it will be exciting to meet them.
3.00+
2+ Reviews
10+ Question Solved
Related Book For
Optimization Models
ISBN: 9781107050877
1st Edition
Authors: Giuseppe C. Calafiore, Laurent El Ghaoui
Question Posted:
Students also viewed these Mathematics questions
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Please help with the discusin questions ! I give thumbs up Case #1: Hailing a New Era: Haier in Japan As one of the most valuable brands in China, Haier designs,manufactures, and sells various home...
-
The following additional information is available for the Dr. Ivan and Irene Incisor family from Chapters 1-5. Ivan's grandfather died and left a portfolio of municipal bonds. In 2012, they pay Ivan...
-
Under Public Law 480, the United States sells surplus grains to developing countries, which pay in local currencies. Since the United States rarely spends all of these currencies, much of this grain...
-
Woods Co. employed Brian Smith in 2013. Brian earned $5,400 per month and worked the entire year. Assume the Social Security tax rate is 6 percent for the first $110,000 of earnings and the Medicare...
-
Define coefficient of fluctuation of energy and coefficient fluctuation of speed.
-
Sandys mother works for Arf, a nationwide chain of dog kennels. She is receiving company stock as part of her employee retirement plan. She wants to track the stocks performance to see how her...
-
CASH DIVIDENDS AND INCOME TAXES During the year ended December 31, 20-2, Bebeto Company completed the following selected transactions: Apr. 15 Estimated that its 20-2 income tax will be $30,000....
-
. year 5? 12. A mutual fund has been advertising that, had you deposited $250 per month in the fund for the last 10 years, you would now have accumulated $85,000. Assuming that these deposits were...
-
We are given a set of points p 1 ,..., p m R n , which are collected in the n x m matrix P = [p 1 , . . . , p m ]. We consider the problem min F(X) = ||xi Pill +_ \\x-x;||3, 2 - i=1 1
-
Assume now that we would like to delete a measurement, and update the least-squares solution accordingly . Assume now we delete the last measurement, that is, replace (a m , y m ) by (0, 0). We...
-
Index cards and pen or pencil. Form teams of six members and select one member to serve as leader. For each team, prepare a deck of eight cards as follows: Facts [each one on a card with the card...
-
Compute the maturity date and the maturity value associated with each of the following notes receivables. (Use 360 days for calculation.) 1. A $20,800, 6%, 3-month note dated April 20. 2. A...
-
Dr. Jim performed an appendectomy on Alison Thursday morning. Everything went well and Alison seemed to be recovering as expected. Saturday morning, she woke with horrible pain and an x-ray revealed...
-
Kraft Heinz is closing its plant in St. Marys, Ontario, believed to employ some 200 people. In 2013, Heinz closed its century-old plant in Leamington, Ontario, laying off around 740 people. After...
-
Hotel capacity is limited in Noshuille so even a 2-star hotel can sell its standard room at the high price of $300. The hotel has 120 rooms and the distribution of the number of x of no shows is. a 3...
-
The following statement of financial position has been prepared for Kareena Beauty Sdn. Bhd for TWO (2) consecutive years. Statement of Financial Position as at 31 March 2014 and 31 March 2015 2015...
-
Distinguish between general audit objectives and management assertions. Why are the general audit objectives more useful to auditors?
-
If the amplifier indicated by the box input impedance of oo, which of the following statements are true ? has an open loop gain as well as Feedback factor (\beta = 1/ R_1\) The feedback is voltage...
-
What is the probability that neither sibling is affected? Suppose that a disease is inherited via a sex-linked mode of inheritance. The implications of this mode of inheritance are that each male...
-
Answer Problem 3.40 for families with two male siblings? Suppose that a disease is inherited via a sex-linked mode of inheritance. The implications of this mode of inheritance are that each male...
-
Answer Problem 3.41 for families with two male siblings? Suppose that a disease is inherited via a sex-linked mode of inheritance. The implications of this mode of inheritance are that each male...
-
Local Manufacturing looks back at the previous year and finds that they processed a total of 1,000 applicants to hire 50, which is 5 percent. This statistic reflects a(an): Group of answer choices HR...
-
Organizational performance practices that result in employees having the skills necessary to do their jobs, increased employee m dynamics within the organization are referred to as O resource-based...
-
Making optimal decisions "at the margin" requires OA. making decisions according to one's whims and fancies. OB. weighing the costs and benefits of a decision before deciding if it should be pursued....
Study smarter with the SolutionInn App