排序方式: 共有22条查询结果,搜索用时 296 毫秒
1.
2.
Roee David Elazar Goldenberg Robert Krauthgamer 《Random Structures and Algorithms》2017,51(4):607-630
We study the problem of reconstructing a low‐rank matrix, where the input is an n × m matrix M over a field and the goal is to reconstruct a (near‐optimal) matrix 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 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 ‐close to a matrix of rank (together with d and ), this algorithm computes with high probability a rank‐d matrix that is ‐close to M. This is a local algorithm that proceeds in two phases. The preprocessing phase reads only random entries of M, and stores a small data structure. The query phase deterministically outputs a desired entry 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 , we analyze sampling algorithms by using statistical learning tools. A preliminary version of this paper appears appears in ECCC, see: http://eccc.hpi-web.de/report/2015/128/ © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 607–630, 2017 相似文献
3.
Energy gaps in a spacetime crystal 总被引:1,自引:0,他引:1
This Letter presents an analysis of the band structure of a spacetime potential lattice created by a standing electromagnetic wave. We show that there are energy band gaps. We estimate the effect, and propose a measurement that could confirm the existence of such phenomena. 相似文献
4.
Summary. In this paper we again consider the rate of convergence of the conjugate gradient method. We start with a general analysis
of the conjugate gradient method for uniformly bounded solutions vectors and matrices whose eigenvalues are uniformly bounded
and positive. We show that in such cases a fixed finite number of iterations of the method gives some fixed amount of improvement
as the the size of the matrix tends to infinity. Then we specialize to the finite element (or finite difference) scheme for
the problem . We show that for some classes of function we see this same effect. For other functions we show that the gain made by performing a fixed number of iterations of the
method tends to zero as the size of the matrix tends to infinity.
Received July 9, 1998 / Published online March 16, 2000 相似文献
5.
Fr. Rappport A. Glaser O. Folin A. Svedberg L. Cuny J. Robert H. Cordebard F. W. Allen J. M. Luck P. Wenger Ch. Cimerman A. Maulbetsch K. Lang K. Hinsberg D. Laszlo M. T. Hanke K. K. Koessler J. M. Looney Z. Dische C. van Zijp H. Engelberg G. Plancher 《Analytical and bioanalytical chemistry》1935,101(7-8):312-320
6.
Roee Engelberg Jochen Knemann Stefano Leonardi Joseph Naor 《Journal of Discrete Algorithms》2007,5(2):262-279
We study budgeted variants of classical cut problems: the Multiway Cut problem, the Multicut problem, and the k-Cut problem, and provide approximation algorithms for these problems. Specifically, for the budgeted multiway cut and the k-cut problems we provide constant factor approximation algorithms. We show that the budgeted multicut problem is at least as hard to approximate as the sparsest cut problem, and we provide a bi-criteria approximation algorithm for it. 相似文献
7.
Rappport A. Glaser O. Folin A. Svedberg L. Cuny J. Robert H. Cordebard F. W. Allen J. M. Luck P. Wenger Ch. Cimerman A. Maulbetsch K. Lang K. Hinsberg D. Laszlo M. T. Hanke K. K. Koessler J. M. Looney Z. Dische C. van Zijp H. Engelberg und G. Plancher 《Fresenius' Journal of Analytical Chemistry》1935,101(7-8):312-320
Ohne Zusammenfassung 相似文献
8.
M. Stschigol Rappaport A. Glaser O. Folin A. Svedberg L. Cuny J. Robert H. Cordebard F. W. Allen J. M. Luck P. Wenger Ch. Cimerman A. Maulbetsch K. Lang K. Hinsberg D. Laszlo M. T. Hanke K. K. Koessler J. M. Looney Z. Dische C. van Zijp F. Rappaport H. Engelberg und G. Plancher 《Fresenius' Journal of Analytical Chemistry》1935,101(7-8):312
Ohne Zusammenfassung 相似文献
9.
10.
Summary. Continuing our previous analysis, we derive the exact number of conjugate gradient iterations needed (to achieve a given
tolerance) for the one-dimensional discrete Poisson equation on a uniform grid, and a particularly smooth solution vector.
Received July 29, 1998 / Published online March 16, 2000 相似文献