Abstract
An interval approach to the concept of dimension is presented. The concept of quasiorthogonal dimension is obtained by relaxing exact orthogonality so that angular distances between unit vectors are constrained to a fixed closed symmetric interval about \(\pi /2\). An exponential number of such quasiorthogonal vectors exist as the Euclidean dimension increases. Lower bounds on quasiorthogonal dimension are proven using geometry of high-dimensional spaces and a separate argument is given utilizing graph theory. Related notions are reviewed.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
D. Achlioptas, Datbase-friendly random projections, in ACM Symposium on the Principles of Database Systems, (2001) pp. 274–281; see also Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comp. Sys. Sci. 66(4), 671–687 (2003)
N. Alon, Problems and results in extremal combinatorics. Disc. Math. 273, 1–3 (2003)
R.B. Ash, Information Theory, Dover Publication New York, 1990 (orig. 1965)
K. Ball, An elementary introduction to modern convex geometry, in Flavors of Geometry, ed. by S. Levy, MSRI Publication 31, Cambridge University Press, (1997), pp. 1–56
C. Berge, Graphs and Hypergraphs (North-Holland, Amsterdam, 1973)
E. Bingham, H. Mannila, Random projection in dimensionality reduction: applications to image and text data, in KDD-2001: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Association for Computing Machinery, New York), pp. 245–250
S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities: A nonasymptotic theory of independence (Clarendon Press, Oxford, 2012)
B. Bollobaś, P. Erdős, Cliques in random graphs. Math. Proc. Camb. Phil. Soc. 80, 419–427 (1976)
J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math. 52, 46–52 (1985)
C. Brezinsky, K.A. Driver, M. Redivo-Zaglia, Quasi-orthogonality with applications to some families of classical orthogonal polynomials. Appl. Num. Math. 48, 157–168 (2004)
S. Dasgupta, A. Gupta, An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algor. 22(1), 60–65 (2003), http://cseweb.ucsd.edu/~dasgupta/papers/jl.pdf
J. Dénes, A.D. Keedwell, Latin Squares and Their Application (English University Press, London, 1974)
R. Diestel, Graph Theory, vol. 173, 3rd edn. Graduate Texts in Mathematics (Springer, Berlin, 2005)
F. Deutsch, Best Approximation in Inner Product Spaces (Springer, New York, 2001)
L. Engebretsen, P. Indyk, R. O’Donnell, Derandomized dimension reduction with applications, in Proceeding SODA ’02, (Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (San Francisco, 2002), pp. 705–712
P. Erdős, H. Hanani, On a limit theorem in combinatorial analysis. Publ. Math. Debrecen 10, 10–13 (1963)
J. Farkhani, A quasi-orthogonal space-time block code. IEEE Trans. Commun. 49(1), 1–4 (2001)
J.R. Firth, Wikipedia, Retrieved 6 Sept 2017
J. Fan, S. Guo, N. Hao, Variance estimation using refitted cross-validation in ultrahigh dimensional regression. J. R. Statist. Soc. B 74, Part 1, 37–65 (2012)
D. Fradkin, D. Madigan, Experiments with random projections for machine learning, in Proceedings KDD 2003 Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (Washington, DC, 2003) pp. 517–522
S.I. Gallant, Methods for generating or revising context vectors for a plurality of word stems, US Patent US5325298 A, Filing date Sept. 3, 1991; Publ. date 26 June 1994. Assignee: HNC Inc. (Hecht-Nielsen Neurocomputing Corp.)
A.N. Gorban, I.Y. Tyukin, D.V. Prokhorov, K.I. Sofeikov, Approximation with random bases: pro et contra. Inf. Sci. 364–365, 129–145 (2016)
M. Gromov, Isoperimetry of waists and concentration of maps. GAFA, Geom. Funct. Anal. 13, 178–215 (2013)
A. Hajnal, E. Szemerdi, Proof of a conjecture of Erds, in Combinatorial Theory and Its Applications, ed. by P. Erdős, A. Rényi, V.T. Sós, vol. 2 (North-Holland, Amsterdam, 1970), pp. 601–623
P. Hall, J.S. Marron, A. Neeman, Geometric representation of high dimension, low sample size data. J. R. Statist. Soc. B 67(3), 427–444, (2005)
R.W. Hamming, Coding and Information Theory (Prentice-Hall, Englewood Cliff, NJ, 1986)
F. Harary, Graph Theory Addison-Wesley (Reading, MA, 1969)
R. Hecht-Nielsen, Context vectors: general purpose approximate meaning representations self-organized from raw data, in Computational Intelligence: Imitating Life, ed. by J. Zurada, R. Marks, C. Robinson, (IEEE Press, 1994), pp. 43–56
J.D. Horton, Sub Latin squares and incomplete orthogonal arrays. J. Comb. Th. A 16(1974), 23–33 (1974)
W.B. Johnson, J. Lindenstrauss, Extensions of Lipschitz maps into a Hilbert space. Contemp. Math. 26, 189–206 (1984)
P.C. Kainen, Orthogonal dimension and tolerance, Technical Report (1992), https://www.researchgate.net
P.C. Kainen, V. Kůrková, Quasiorthogonal dimension of Euclidean spaces. Appl. Math. Lett. 6(3), 7–10 (1993), https://www.sciencedirect.com
S. Kaski, Dimensionality reduction by random mapping: fast similarity computation for clustering, in Proceedings 1998 IEEE IJCNN (1998) pp. 413–418
F. Knoll, Johnson-Lindenstrauss Transformations, Ph.D. Dissertation, (Clemson University, 2017)
R.B. Kearfott, V. Kreinovich (ed.), Applications of Interval Computations (Kluwer, Dordrecht, 1996)
A.N. Kolmogorov, V.M. Tikhomorov, \(\varepsilon \)-entropy and \(\varepsilon \)-capacity of sets in functional spaces, AMS Transl. (Ser. 2), 17, 277–364 (1961); orig. Usp. Mat. Nauk.14(2), 3–86 (1959)
V. Kreinovich, Interval Computing, http://cs.utep.edu/interval-comp/main.html
V. Kůrková, R. Hecht-Nielsen, Quasiorthogonal sets, Technical Report INC-9204 (1992)
V. Kůrková, M. Sanguineti, Estimates of covering numbers of convex sets with slowly decaying orthogonal subsets. Discret. Appl. Math. 155, 1930–1942 (2007)
M.A. Lazarus et al., Predictive modeling of consumer financial behavior, US Patent US6430539 B1, Filing date May 6 1999; Publ. date Aug. 6 2002
N.N. Lebedev, Special Functions and Their Applications, transl. R.A. Silverman, Dover Publications, Inc., 1972 (orig. Prentice-Hall, 1965)
P. Lèvy, Problèmes Concrets d’Analyse Functionelle (Gauthier-Villard, Paris, 1951)
P. Li, T.J. Hastie, K.W. Church, Very sparse random projections, in Proceedings KDD 2006, (Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining) (2006), pp. 287–296
N. Linial, E. London, E. Rabinovich, The geometry of graphs and some of its algorithmic applications. Combinatorica 15, 215–246 (2001)
B.J. MacLennan, Information processing in the dendritic net, in Rethinking Neural Networks: Quantum Fields and Biological Data, ed. by K.H. Pribram (Lawrence Erlbaum, Hillsdale, 1993), pp. 161–197
C.D. Manning, P. Raghavan, H. Schűtze, Introduction to Information Retrieval (Cambridge University Press, New York, NY, 2008); online edition, April 1 2009, https://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
J. Matoušek, Lectures on Discrete Geometry (Springer, New York, 2002)
D. Matula, The largest clique size in a random graph, Technical Report CS-7608, Department of Computer Science, Southern Methodist University (1976), https://s2.smu.edu/~matula/Tech-Report76.pdf
V.D. Milman, G. Schechtman, Asymptotic theory of finite dimensional normed spaces, vol. 1200, Lecture Notes in Mathematics (Springer, Berlin, 1986)
R.N. Mohan, M.H. Lee, S.S. Pokhre, On orthogonality of latin squares (2006), arXiv:cs/0604041v2 [cs.DM]
R.E. Moore, Interval arithmetic and automatic error analysis in digital computing, Ph.D. Dissertation (Stanford University, 1962)
J. Pennington, R. Socher, C.D. Manning, GloVe: global vectors for word representation, in Conference on Empirical Methods in Natural Language Processing (EMNLP, 2014)
R.A. Rankin, The closest packing of spherical caps in \(n\) dimensions. Proc. Glasgow Math. Assoc. 2, 139–144 (1955)
R.A. Rankin, On packing of spheres in Hilbert space. Proc. Glasgow Math. Assoc. 2, 145–146 (1955)
V. Rődl, On a packing and covering problem. Europ. J. Comb. 5, 69–78 (1985)
R.J. Ryser, Combinatorial Mathematics (Mathematical Association of America, Washington, DC, 1963)
M. Sahlgren, An introduction to random indexing, in Methods and Applications of Semantic Indexing Workshop at the 7th Int’l Conference on Terminology and Knowledge Engineering, vol. 87 (TermNet News: Newsletter of International Cooperation in Terminology, 2005)
M. Sahlgren, The distributional hypothesis. Rivista di Linguistica 20(1), 33–53 (2008)
H.H. Schaefer, M.P. Wolff, Topological Vector Spaces, 2nd edn. (Springer, New York, 1999)
E. Schmidt, Die Brunn-Minkowskische Ungleichung und ihr Spiegelbild sowie die isoperimetrische Eigenschaft der Kugel in der euklidischen und nichteuklidischen Geometrie. Mathematische Nachrichten 1(1948), 81–115 (1948)
J. Spencer, Ten Lectures on the Probabilistic Method (CBMS-NSF, SIAM, Philadelphia, PA, 1987)
W. Su, X.-G. Xia, Signal constellations for quasi-orthogonal space-time block codes with full diversity. IEEE Trans. Inf. Theory 50(10), 2331–2347 (2004)
A.D. Wyner, Random packings and coverings of the unit \(n\)-sphere. Bell Syst. Tech. J. 46, 2111–2118 (1967)
Y.G. Yan, On the exact value of packing spheres in a class of Orlicz function spaces. J. Convex Anal. 11(2), 394–400 (2004)
K. Yoshida, Functional Analysis (Springer, Berlin, 1965)
K. Zhang, Spherical cap packing asymptotics and rank-extreme detection. IEEE Trans. Inf. Theory (in press, 2017) https://arxiv.org/pdf/1511.06198.pdf
Acknowledgements
V. Kůrková was partially supported by the Czech Grant Foundation grant GA19-05704S and institutional support of the Institute of Computer Science RVO 67985807. P. C. Kainen received research support from Georgetown University.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Kainen, P.C., Kůrková, V. (2020). Quasiorthogonal Dimension. In: Kosheleva, O., Shary, S., Xiang, G., Zapatrin, R. (eds) Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications. Studies in Computational Intelligence, vol 835. Springer, Cham. https://doi.org/10.1007/978-3-030-31041-7_35
Download citation
DOI: https://doi.org/10.1007/978-3-030-31041-7_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-31040-0
Online ISBN: 978-3-030-31041-7
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)