 |
|
|
| | | | | |
|
|
|
|
|
Interpolation of Random Hyperplanes
|
Ery Arias-Castro, University of California, San Diego
|
Abstract
Let (Zi,Wi): i=1,...,n be uniformly distributed in [0,1]d X G(k,d), where G(k,d) denotes the space of k-dimensional linear subspaces of Rd. For a differentiable function f from [0,1]k into [0,1]d, we say that f interpolates (z,w) in [0,1]d X G(k,d) if there exists x in [0,1]k such that f(x) = z and vec{f}(x) = w, where vec{f}(x) denotes the tangent space at x defined by f. For a smoothness class F of Holder type, we obtain probability bounds on the maximum number of points a function f in F interpolates.
|
Full text: PDF
Pages: 1052-1071
Published on: August 15, 2007
|
Bibliography
-
P.-A. Absil, A. Edelman, and P. Koev.
On the largest principal angle between random subspaces.
Linear Algebra Appl., 414 (2006), no. 1, 288-294.
MR2209246 (2006j:15071)
-
E. Arias-Castro, D. L. Donoho, X. Huo, and C. Tovey.
Connect-the-dots: How many random points can a regular curve pass
through?
Adv. in Appl. Probab., 37 (2005), no. 3, 571-603.
MR2156550 (2006e:60012)
-
E. Arkin, J. Mitchell, and G. Narasimhan.
Resource-constrained geometric network optimization.
In Proc. of ACM Symposium on Computational Geometry,
Minneapolis, (1997), 307-316.
-
B. Awerbuch, Y. Azar, A. Blum, and S. Vempala.
New approximation guarantees for minimum-weight k-trees and
prize-collecting salesmen.
SIAM J. Comput., 28 (1999), no. 1, 254-262.
MR1630453 (99e:68063)
- B. DasGupta, J. Hespanha, and E. Sontag.
Computational complexities of honey-pot searching with local sensory
information.
In 2004 American Control Conference (ACC 2004), pages
2134-2138. 2004.
- D. Field, A. Hayes, and R. Hess.
Contour integration by the human visual system: evidence for a local
association field.
Vision Research, 33(2):173-193, 1993.
-
G. H. Golub and C. F. Van Loan.
Matrix computations.
Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins
University Press, Baltimore, MD, third edition, 1996.
MR1417720 (97g:65006)
- X. Huo, D. Donoho, C. Tovey, and E. Arias-Castro.
Dynamic programming methods for `connecting the dots' in scattered
point clouds.
INFORMS J. Comput., 2005.
To appear.
- A. N. Kolmogorov.
Selected works of A. N. Kolmogorov. Vol. III,
volume 27 of Mathematics and its Applications (Soviet Series).
Kluwer Academic Publishers Group, Dordrecht, 1993.
MR1228446 (94c:01040)
- V. D. Milman and G. Schechtman.
Asymptotic theory of finite-dimensional normed spaces, volume
1200 of Lecture Notes in Mathematics.
Springer-Verlag, Berlin, 1986.
With an appendix by M. Gromov.
MR856576 (87m:46038)
- F. Mosteller.
Fifty challenging problems in probability with solutions.
Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1965.
MR397810 (53 #1666)
- G. R. Shorack and J. A. Wellner.
Empirical processes with applications to statistics.
John Wiley & Sons Inc., New York, 1986.
MR838963 (88e:60002)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context