欢迎光临!
您现在所在的位置:首页 >> 通知公告 & 学术信息
学术信息
SEMINARS
Estimating the Schatten norms of matrices in streaming model
时间  Datetime
2018-07-10 15:30 — 16:30 
地点  Venue
Middle Lecture Room
报告人  Speaker
Yi Li (李翼)
单位  Affiliation
Nanyang Technological University
邀请人  Host
Yaokun Wu
报告摘要  Abstract

A popular data stream model in theoretical computer science is the turnstile streaming model, in which there is an underlying vector which is initialized to 0 and receives incremental updates to its coordinates. The goal is to compute some function of the vector at the end of the stream without essentially storing the entire vector. A well-studied problem in the literature is approximating the ell_p norms of the vector; in this talk I shall study the analogous problem of estimating matrix Schatten norms. I intend to present a systematic summary of latest results on the space complexity of estimating the Schatten p-norms of an n x n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered.