BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Allen Liu (MIT EECS) DTSTART:20211118T230000Z DTEND:20211119T000000Z DTSTAMP:20260423T021044Z UID:SPAMS/6 DESCRIPTION:Title: Te nsor Completion Made Practical\nby Allen Liu (MIT EECS) as part of MIT Simple Person's Applied Mathematics Seminar\n\nLecture held in Room: 2 - 132 in the Simons Building.\n\nAbstract\nTensor completion is a natural hi gher-order generalization of matrix completion where the goal is to recove r a low-rank tensor from sparse observations of its entries. Existing algo rithms are either heuristic without provable guarantees\, based on solving large semidefinite programs which are impractical to run\, or make strong assumptions such as requiring the factors to be nearly orthogonal. In thi s paper we introduce a new variant of alternating minimization\, which in turn is inspired by understanding how the progress measures that guide con vergence of alternating minimization in the matrix setting need to be adap ted to the tensor setting. We show strong provable guarantees\, including showing that our algorithm converges linearly to the true tensors even whe n the factors are highly correlated and can be implemented in nearly linea r time. Moreover our algorithm is also highly practical and we show that w e can complete third order tensors with a thousand dimensions from observi ng a tiny fraction of its entries. In contrast\, and somewhat surprisingly \, we show that the standard version of alternating minimization\, without our new twist\, can converge at a drastically slower rate in practice.\n LOCATION:https://researchseminars.org/talk/SPAMS/6/ END:VEVENT END:VCALENDAR