Interpolation of Random Hyperplanes

Ery Arias-Castro (University of California, San Diego)


Let $\{(Z_i,W_i):i=1,\dots,n\}$ be uniformly distributed in $[0,1]^d \times \mathbb{G}(k,d)$, where $\mathbb{G}(k,d)$ denotes the space of $k$-dimensional linear subspaces of $\mathbb{R}^d$. For a differentiable function $f: [0,1]^k \rightarrow [0,1]^d$, we say that $f$ interpolates $(z,w) \in [0,1]^d \times \mathbb{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 ${\cal F}$ of Holder type, we obtain probability bounds on the maximum number of points a function $f \in {\cal F}$ interpolates.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1052-1071

Publication Date: August 15, 2007

DOI: 10.1214/EJP.v12-435


  1. 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)
  2. 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)
  3. E. Arkin, J. Mitchell, and G. Narasimhan.  Resource-constrained geometric network optimization.  In Proc. of ACM Symposium on Computational Geometry, Minneapolis, (1997), 307-316.
  4. 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)
  5. 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.
  6. 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.
  7. 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)
  8. 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.
  9. 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)
  10. 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)
  11. F. Mosteller.  Fifty challenging problems in probability with solutions.  Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1965.  MR397810 (53 #1666)
  12. G. R. Shorack and J. A. Wellner.  Empirical processes with applications to statistics.  John Wiley & Sons Inc., New York, 1986.  MR838963 (88e:60002)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.