中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 计算技术研究所
  3. 中国科学院计算技术研究所
  4. 中国科学院计算技术研究所期刊论文
  5. 英文
Querying a Matrix through Matrix-Vector Products

文献类型：期刊论文

作者Sun, Xiaoming1,2; Woodruff, David P.3; Yang, Guang1,4; Zhang, Jialin1,2
刊名ACM TRANSACTIONS ON ALGORITHMS
出版日期2021-10-01
卷号17期号:4页码:19
ISSN号1549-6325
关键词Communication complexity linear algebra sketching
DOI10.1145/3470566
英文摘要We consider algorithms with access to an unknown matrix M epsilon F-nxd via matrix-vector products, namely, the algorithm chooses vectors v(1),..., v(q), and observes Mv(1),..., Mv(q). Here the vi can be randomized as well as chosen adaptively as a function of Mv(1),..., Mv(i-1). Motivated by applications of sketching in distributed computation, linear algebra, and streaming models, as well as connections to areas such as communication complexity and property testing, we initiate the study of the number q of queries needed to solve various fundamental problems. We study problems in three broad categories, including linear algebra, statistics problems, and graph problems. For example, we consider the number of queries required to approximate the rank, trace, maximum eigenvalue, and norms of a matrixM; to compute the AND/OR/Parity of each column or row of M, to decide whether there are identical columns or rows in M or whether M is symmetric, diagonal, or unitary; or to compute whether a graph defined byMis connected or triangle-free. We also show separations for algorithms that are allowed to obtainmatrix-vector products only by querying vectors on the right, versus algorithms that can query vectors on both the left and the right. We also show separations depending on the underlying field the matrix-vector product occurs in. For graph problems, we show separations depending on the form of the matrix (bipartite adjacency versus signed edge-vertex incidence matrix) to represent the graph. Surprisingly, very few works discuss this fundamental model, and we believe a thorough investigation of problems in this model would be beneficial to a number of different application areas.
资助项目National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61872334] ; Strategic Priority Research Program of Chinese Academy of Sciences[XDA27000000] ; K. C. Wong Education Foundation ; National Science Foundation[CCF-181584]
WOS研究方向Computer Science ; Mathematics
语种英语
出版者ASSOC COMPUTING MACHINERY
WOS记录号WOS:000705407100004
源URL[http://119.78.100.204/handle/2XEOYT63/16945]  
专题中国科学院计算技术研究所期刊论文_英文
通讯作者Sun, Xiaoming
作者单位1.Chinese Acad Sci, Inst Comp Technol, Beijing, Peoples R China
2.Univ Chinese Acad Sci, Beijing, Peoples R China
3.Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
4.Conflux, Beijing, Peoples R China
推荐引用方式
GB/T 7714		 Sun, Xiaoming,Woodruff, David P.,Yang, Guang,et al. Querying a Matrix through Matrix-Vector Products[J]. ACM TRANSACTIONS ON ALGORITHMS,2021,17(4):19.
APA Sun, Xiaoming,Woodruff, David P.,Yang, Guang,&Zhang, Jialin.(2021).Querying a Matrix through Matrix-Vector Products.ACM TRANSACTIONS ON ALGORITHMS,17(4),19.
MLA Sun, Xiaoming,et al."Querying a Matrix through Matrix-Vector Products".ACM TRANSACTIONS ON ALGORITHMS 17.4(2021):19.

入库方式： OAI收割

来源：计算技术研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。