CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt173",{id:"formSmash:upper:j_idt173",widgetVar:"widget_formSmash_upper_j_idt173",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt175_j_idt179",{id:"formSmash:upper:j_idt175:j_idt179",widgetVar:"widget_formSmash_upper_j_idt175_j_idt179",target:"formSmash:upper:j_idt175:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Fast and memory optimal low-rank matrix approximationPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2015 (English)In: Advances in Neural Information Processing Systems, Neural information processing systems foundation , 2015, p. 3177-3185Conference paper, Published paper (Refereed)
##### Abstract [en]

##### Place, publisher, year, edition, pages

Neural information processing systems foundation , 2015. p. 3177-3185
##### Keyword [en]

Approximation theory, Information science, Matrix algebra, Mean square error, Arbitrary order, Computationally efficient, High probability, Low rank approximations, Low-rank matrix approximations, Memory footprint, Singular values, Sparsification, Approximation algorithms
##### National Category

Control Engineering
##### Identifiers

URN: urn:nbn:se:kth:diva-194718Scopus ID: 2-s2.0-84965132645OAI: oai:DiVA.org:kth-194718DiVA, id: diva2:1048893
##### Conference

29th Annual Conference on Neural Information Processing Systems, NIPS 2015, 7 December 2015 through 12 December 2015
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt478",{id:"formSmash:j_idt478",widgetVar:"widget_formSmash_j_idt478",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt484",{id:"formSmash:j_idt484",widgetVar:"widget_formSmash_j_idt484",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt490",{id:"formSmash:j_idt490",widgetVar:"widget_formSmash_j_idt490",multiple:true});
##### Note

In this paper, we revisit the problem of constructing a near-optimal rank k approximation of a matrix M ∈ [0,1]m×n under the streaming data model where the columns of M are revealed sequentially. We present SLA (Streaming Low-rank Approximation), an algorithm that is asymptotically accurate, when ksk+1(M) =o(√mn) where sk+1(M) is the (k + 1)-th largest singular value of M. This means that its average mean-square error converges to 0 as m and n grow large (i.e., || M(k)-M(k)||2 F = o(mn) with high probability, where M(k) and M(k) denote the output of SLA and the optimal rank k approximation of M, respectively). Our algorithm makes one pass on the data if the columns of M are revealed in a random order, and two passes if the columns of M arrive in an arbitrary order. To reduce its memory footprint and complexity, SLA uses random sparsification, and samples each entry of M with a small probability δ. In turn, SLA is memory optimal as its required memory space scales as k(m+n), the dimension of its output. Furthermore, SLA is computationally efficient as it runs in O(δkmn) time (a constant number of operations is made for each observed entry of M), which can be as small as O(k log(m)4n) for an appropriate choice of δ and if n ≥ m.

QC 20161122

Available from: 2016-11-22 Created: 2016-10-31 Last updated: 2016-11-22Bibliographically approved
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1212",{id:"formSmash:j_idt1212",widgetVar:"widget_formSmash_j_idt1212",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1265",{id:"formSmash:lower:j_idt1265",widgetVar:"widget_formSmash_lower_j_idt1265",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1266_j_idt1268",{id:"formSmash:lower:j_idt1266:j_idt1268",widgetVar:"widget_formSmash_lower_j_idt1266_j_idt1268",target:"formSmash:lower:j_idt1266:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});