检索结果-内蒙古大学图书馆

Fast Phase Retrieval from Local Correlation Measurements

SIAM JOURNAL ON IMAGING SCIENCES 2016年第4期9卷 1655-1688页

作者： Iwen, Mark A. Viswanathan, Aditya Wang, Yang Michigan State Univ Dept Math E Lansing MI 48824 USA Michigan State Univ Dept Elect & Comp Engn E Lansing MI 48824 USA Hong Kong Univ Sci & Technol Dept Math Kowloon Hong Kong Peoples R China

We develop a fast phase retrieval method which can utilize a large class of local phaseless correlation-based measurements in order to recover a given signal x is an element of C-d (up to an unknown global phase) in near-linear O (d log(4) d)-time. Accompanying theoretical analysis proves that the proposed algorithm is guaranteed to deterministically recover all signals x satisfying a natural flatness (i.e., nonsparsity) condition for a particular choice of deterministic correlation-based measurements. A randomized version of these same measurements is then shown to provide nonuniform probabilistic recovery guarantees for arbitrary signals x is an element of C-d. Numerical experiments demonstrate the method's speed, accuracy, and robustness in practice-all code is made publicly available. In its simplest form, our proposed phase retrieval method employs a modified lifting scheme akin to the one utilized by the well-known Phase Lift algorithm. In particular, it interprets quadratic magnitude measurements of x as linear measurements of a restricted set of lifted variables, xi (x(j)) over bar, for |j - i| < delta << d. This leads to a linear system involving a total of (2 delta - 1) d unknown lifted variables, all of which can then be solved for using only O (delta d) measurements. Once these lifted variables, xi<(x(j))over bar> for |j - i| < delta << d, have been recovered, a fast angular synchronization method can then be used to propagate the local phase difference information they provide across the entire vector in order to estimate the (relative) phases of every entry of x. In addition, the lifted variables corresponding to xi<(x(j))over bar> = |x(j)|(2) automatically provide magnitude estimates for each entry, x(j), of x. The proposed phase retrieval method then approximates x by carefully combining these entrywise phase and magnitude estimates. Finally, we conclude by developing an extension of the proposed method to the sparse phase retrieval problem;specifica

关键词： phase retrieval ptychography angular synchronization compressive phase retrieval sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Compressed sensing with sparse binary matrices: Instance optimal error guarantees in near-optimal time

引用

JOURNAL OF COMPLEXITY 2014年第1期30卷 1-15页

作者： Iwen, M. A. Michigan State Univ Dept Math E Lansing MI 48824 USA

A compressed sensing method consists of a rectangular measurement matrix, M is an element of R-mxN with m R-m -> R-N. Compressed sensing methods aim to construct a high quality approximation to any given input vec... 详细信息

A compressed sensing method consists of a rectangular measurement matrix, M is an element of R-mxN with m << N, together with an associated recovery algorithm, A : > R-m -> R-N. Compressed sensing methods aim to construct a high quality approximation to any given input vector X E RN using only Mx is an element of R'n as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for M and A, of the form parallel to x A (Mx)parallel to <= parallel to x - x(k)(opt)parallel to + Ck(1/p-1/q) parallel to x - x(k)(opt)parallel to for X is an element of RN, where x(k)(opt) is the best possible k-term approximation to x. In this paper we develop a compressed sensing method whose associated recovery algorithm, A, runs in O ((k log k) log N)-time, matching a lower bound up to a O (log k) factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for highvolume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein. (C) 2013 Elsevier Inc. All rights reserved.

关键词： Compressed sensing sublinear-time algorithms Sparse matrices

来源：评论

学校读者我要写书评

暂无评论

Fast approximate PCPs for multidimensional bin-packing problems

引用

INFORMATION AND COMPUTATION 2005年第1期196卷 42-56页

作者： Batu, T Rubinfeld, R White, P Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada MIT CSAIL Cambridge MA 02139 USA Cornell Univ Comp Sci Dept Ithaca NY 14853 USA

We consider approximate PCPs for multidimensional bin-packing problems. In particular, we show how a verifier can be quickly convinced that a set of multidimensional blocks can be packed into a small number of bins. The running time of the verifier is bounded by O(log(d) n) where n is the number of blocks and d is the dimension. (C) 2004 Elsevier Inc. All rights reserved.

关键词： proof-assisted property testing probabilistically checkable proofs multidimensional bin-packing problems sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

Approximating average parameters of graphs

引用

RANDOM STRUCTURES & algorithms 2008年第4期32卷 473-493页

作者： Goldreich, Oded Ron, Dana Tel Aviv Univ Dept EE Syst Ramat Aviv Israel Weizmann Inst Sci Dept Comp Sci IL-76100 Rehovot Israel

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. (c) 2008 Wiley Periodicals, Inc.

关键词： sublinear-time algorithms randomized approximation algorithms Wiener Index

来源：评论

学校读者我要写书评

暂无评论

Local reconstruction of low-rank matrices and subspaces

引用

RANDOM STRUCTURES & algorithms 2017年第4期51卷 607-630页

作者： David, Roee Goldenberg, Elazar Krauthgamer, Robert Weizmann Inst Sci Rehovot Israel Acad Coll Tel Aviv Yaffo Tel Aviv Israel

We study the problem of reconstructing a low-rank matrix, where the input is an nxm matrix M over a field F and the goal is to reconstruct a (near-optimal) matrix M that is low-rank and close to M under some distance function . Furthermore, the reconstruction must be local, i.e., provides access to any desired entry of M by reading only a few entries of the input M (ideally, independent of the matrix dimensions n and m). Our formulation of this problem is inspired by the local reconstruction framework of Saks and Seshadhri (SICOMP, 2010). Our main result is a local reconstruction algorithm for the case where is the normalized Hamming distance (between matrices). Given M that is E-close to a matrix of rank (together with d and E), this algorithm computes with high probability a rank-d matrix M that is O-close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only O) random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry Mi,j by reading only the data structure and 2d additional entries of M. We also consider local reconstruction in an easier setting, where the algorithm can read an entire matrix column in a single operation. When is the normalized Hamming distance between vectors, we derive an algorithm that runs in polynomial time by applying our main result for matrix reconstruction. For comparison, when is the truncated Euclidean distance and F, we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: (c) 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607-630, 2017

关键词： sublinear-time algorithms local reconstruction low-rank matrix reconstruction matrix rigidity subspace approximation

来源：评论

学校读者我要写书评

暂无评论

AN ADAPTIVITY HIERARCHY THEOREM FOR PROPERTY TESTING

引用

COMPUTATIONAL COMPLEXITY 2018年第4期27卷 671-716页

作者： Canonne, Clement L. Gur, Tom Stanford Univ Stanford CA 94305 USA Univ Calif Berkeley Berkeley CA USA

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers received to prior queries, and their non-adaptive counterparts, in which all queries are independent of answers obtained from previous queries. In this work, we investigate the role of adaptivity in property testing at a finer level. We first quantify the degree of adaptivity of a testing algorithm by considering the number of "rounds of adaptivity" it uses. More accurately, we say that a tester is k-(round) adaptive if it makes queries in k + 1 rounds, where the queries in the i'th round may depend on the answers obtained in the previous i - 1 rounds. Then, we ask the following question: Does the power of testing algorithms smoothly grow with the number of rounds of adaptivity? We provide a positive answer to the foregoing question by proving an adaptivity hierarchy theorem for property testing. Specifically, our main result shows that for every n is an element of N and 0 <= k <= n(0.33) there exists a property P-n,P-k of functions for which (1) there exists a k-adaptive tester for P-n,P-k with query complexity (O) over tilde (k), yet (2) any (k - 1)-adaptive tester for P-n,P-k must make (Omega) over tilde (n/k(2)) queries. In addition, we show that such a qualitative adaptivity hierarchy can be witnessed for testing natural properties of graphs.

关键词： sublinear-time algorithms property testing complexity theory

来源：评论

学校读者我要写书评

暂无评论

Optimal Testing of Reed-Muller Codes

Optimal Testing of Reed-Muller Codes

引用

IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS)

作者： Bhattacharyya, Arnab Kopparty, Swastik Schoenebeck, Grant Sudan, Madhu Zuckerman, David MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Univ Calif Berkeley Dept Comp Sci Berkeley CA USA Microsoft Res Cambridge MA USA Univ Texas Austin Dept Comp Sci Austin TX USA

ISBN: (纸本)9780769542447

We consider the problem of testing if a given functions f : F-2(n) -> F-2 is close to any degree d polynomial in n variables, also known as the Reed-Muller testing problem. Alon et al . [1] proposed and analyzed a natural 2(d+1)-query test for this problem. this test turned out to be intimately related to the Gowers norm. Alon et. al. showed that this test accepts every degree d polynomial with probability 1, while it rejects functions that are Omega(1)-far with probability Omega(1/(d2(d))). We give an asymptotically optimal analysis of this test, and show that it rejects functions that are (even only) Omega(2(-d))-far with Omega(1)-probability (so the rejection probability is a universal constant independent of d and n). This implies a tight relationship between the (d + 1)(st)-Gowers norm of a function and its maximal correlation with degree d polynomials, when the correlation is close to 1. Our proof works by inductions on n and yields a new analysis of even the classical Blum-Luby-Rubinfeld [2] linearity test, for the setting of functions mapping F-2(n) to F-2. The optimality follows from a tighter analysis of counterexamples to the "inverse conjecture for the Gowers norm" constructed by [3], [4]. Our results has several implications. First, it shows that the Gowers norm test is tolerant, in that it also accepts close codewords. Second, it improves the parameters of an XOR lemma for polynomials given by Viola and Wigderson [5]. Third, it implies a "query hierarchy" result for property testing of affine-invariant properties. That is, for every functions q(n), it gives an affine-invariant property that is testable with O(q(n))-queries, but not with o(q(n))-queries, complementing an analogous result of [6] for graph properties.

关键词： sublinear-time algorithms Property testing Reed-Muller codes Gowers norm Low-degree tests

来源：评论

学校读者我要写书评

暂无评论

A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers (Extended Abstract) 1

引用

22nd International Symposium on algorithms and Computation (ISAAC)

作者： Hurwitz, Jeremy CALTECH Dept Comp & Math Sci Pasadena CA 91125 USA

ISBN: (数字)9783642255915

ISBN: (纸本)9783642255908

We show that for all integers t >= 8 and arbitrarily small epsilon > 0, there exists a graph property Pi (which depends on epsilon) such that epsilon-testing Pi has non-adaptive query complexity Q = (Theta) over tilde (q(2-2/t)), where q = (Theta) over tilde(epsilon(-1)) is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties. This also gives evidence that the canonical transformation of Goldreich and Trevisan is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree O(epsilon N) and being a blow-up collection of an arbitrary base graph H.

关键词： sublinear-time algorithms Property Testing Dense-Graph Model Adaptive vs Non-adaptive Queries Hierarchy Theorem

来源：评论

学校读者我要写书评

暂无评论

Edge Sampling and Graph Parameter Estimation via Vertex Neighborhood Accesses 2022

Edge Sampling and Graph Parameter Estimation via Vertex Neig...

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Tetek, Jakub Thorup, Mikkel Univ Copenhagen Copenhagen Denmark

ISBN: (纸本)9781450392648

In this paper, we consider the problems from the area of sublineartime algorithms of edge sampling, edge counting, and triangle counting. Part of our contribution is that we consider three different settings, differing in the way in which one may access the neighborhood of a given vertex. In previous work, people have considered indexed neighbor access, with a query returning the i-th neighbor of a given vertex. Full neighborhood access model, which has a query that returns the entire neighborhood at a unit cost, has recently been considered in the applied community. Between these, we propose hash-ordered neighbor access, inspired by coordinated sampling, where we have a global fully random hash function, and can access neighbors in order of their hash values, paying a constant for each accessed neighbor. For edge sampling and counting, our new lower bounds are in the most powerful full neighborhood access model. We provide matching upper bounds in the weaker hash-ordered neighbor access model. Our new faster algorithms can be provably implemented efficiently on massive graphs in external memory and with the current APIs for, e.g., Twitter or Wikipedia. For triangle counting, we provide a separation: a better upper bound with full neighborhood access than the known lower bounds with indexed neighbor access. The technical core of our paper is our edge-sampling algorithm on which the other results depend. We now describe our results on the classic problems of edge and triangle counting. We give an algorithm that uses hash-ordered neighbor access to approximately count edges in time (O) over tilde (n/epsilon(2)root m + 1/epsilon(2)) (compare to the state of the art without hash-ordered neighbor access of (O) over tilde (n/epsilon(2)root m) Eden, Ron, and Seshadhri [ICALP 2017]). We present an Omega(n/epsilon root m) lower bound for epsilon >= root m/n in the full neighborhood access model. This improves the lower bound of Omega(n/root epsilon m) by Goldreich and Ron [R

关键词： sublinear-time algorithms Edge sampling Edge counting Triangle counting

来源：评论

学校读者我要写书评

暂无评论

Sampling Without Compromising Accuracy in Adaptive Data Analysis 31

Sampling Without Compromising Accuracy in Adaptive Data Anal...

引用

31st International Conference on Algorithmic Learning Theory (ALT)

作者： Fish, Benjamin Reyzin, Lev Rubinstein, Benjamin I. P. Microsoft Res Montreal PQ H3A 3H3 Canada Univ Illinois Dept Math Stat & Comp Sci Chicago IL 60607 USA Univ Melbourne Sch Comp & Informat Syst Parkville Vic 3010 Australia

In this work, we study how to use sampling to speed up mechanisms for answering adaptive queries into datasets without reducing the accuracy of those mechanisms. This is important to do when both the datasets and the number of queries asked are very large. In particular, we describe a mechanism that provides a polynomial speed-up per query over previous mechanisms, without needing to increase the total amount of data required to maintain the same generalization error as before. We prove that this speed-up holds for arbitrary statistical queries. We also provide an even faster method for achieving statistically-meaningful responses wherein the mechanism is only allowed to see a constant number of samples from the data per query. Finally, we show that our general results yield a simple, fast, and unified approach for adaptively optimizing convex and strongly convex functions over a dataset.

关键词： Adaptive data analysis differential privacy sublinear-time algorithms

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：