Random Embeddings with Optimal Accuracy
This work constructs Jonson-Lindenstrauss embeddings with best accuracy, as measured by variance, mean-squared error and exponential concentration of the length distortion. Lower bounds for any data and embedding dimensions are determined, and accompanied by matching and efficiently samplable constructions (built on orthogonal matrices). Novel techniques: a unit sphere parametrization, the use of singular-value latent variables and Schur-convexity are of independent interest.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Transformation of Node to Knowledge Graph Embeddings for Faster Link Prediction in Social Networks
Recent advances in neural networks have solved common graph problems such as link prediction, node classification, node clustering, node recommendation by developing embeddings of entities and relations into vector space…
Knowledge Graph EmbeddingsLink PredictionNode ClassificationNode ClusteringOptimal Randomized First-Order Methods for Least-Squares Problems
We provide an exact analysis of a class of randomized algorithms for solving overdetermined least-squares problems. We consider first-order methods, where the gradients are pre-conditioned by an approximation of the Hess…
Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs
This work discusses tensor network embeddings, which are random matrices ($S$) with tensor network structure. These embeddings have been used to perform dimensionality reduction of tensor network structured inputs $x$ an…
Dimensionality ReductionTensor DecompositionConfidence-Optimal Random Embeddings
The seminal result of Johnson and Lindenstrauss on random embeddings has been intensively studied in applied and theoretical computer science. Despite that vast body of literature, we still lack of complete understanding…
Ergodic Limits, Relaxations, and Geometric Properties of Random Walk Node Embeddings
Random walk based node embedding algorithms learn vector representations of nodes by optimizing an objective function of node embedding vectors and skip-bigram statistics computed from random walks on the network. They h…
Link PredictionNode ClassificationStochastic Block Model