Open Problems:34 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:52:08Z

updated header

Krzysztof Onak at 05:27, 16 November 2012

2012-11-16T05:27:38Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 34: Linear Algebra Computation}} {{Infobox |label1 = Proposed by |data1 = Michael Mahoney |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 2009]..."

2012-11-13T01:37:50Z

Created page with "{{DISPLAYTITLE:Problem 34: Linear Algebra Computation}} {{Infobox |label1 = Proposed by |data1 = Michael Mahoney |label2 = Source |data2 = [[Workshops:Kanpur_2009|Kanpur 2009]..."

New page

{{DISPLAYTITLE:Problem 34: Linear Algebra Computation}}
{{Infobox
|label1 = Proposed by
|data1 = Michael Mahoney
|label2 = Source
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
|label3 = Short link
|data3 = http://sublinear.info/34
}}
It is often not the case that the entire data sits on a single machine and that we are allowed to make one or more passes over it. Instead the data is often distributed across multiple systems. This is one of the reasons why the streaming model does not have more impact in practice for linear algebra computation. It would be great to design new models that address this shortcoming.

Consider also the following problem. Let $A$ be an $m\times n$ matrix and let $k$ be a rank parameter. Let $P_{A,k}$ be the projection matrix on the best rank-$k$ left (or right) singular subspace. The goal is to compute the diagonal of $P_{A,k}$ exactly or approximately in a small number of passes in the streaming model, or even better, in a new model that addresses the aforementioned shortcoming.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Michael Mahoney

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 34: Linear Algebra Computation}}
+{{Header
-{{Infobox
+|title=Linear Algebra Computation
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Michael Mahoney
+|who=Michael Mahoney
 }}
 It is often not the case that the entire data sits on a single machine and that we are allowed to make one or more passes over it. Instead the data is often distributed across multiple systems. This is one of the reasons why the streaming model does not have more impact in practice for linear algebra computation. It would be great to design new models that address this shortcoming.
 Consider also the following problem. Let $A$ be an $m\times n$ matrix and let $k$ be a rank parameter. Let $P_{A,k}$ be the projection matrix on the best rank-$k$ left (or right) singular subspace. The goal is to compute the diagonal of $P_{A,k}$ exactly or approximately in a small number of passes in the streaming model, or even better, in a new model that addresses the aforementioned shortcoming.