Página 1 dos resultados de 79 itens digitais encontrados em 0.006 segundos
Geometria de distâncias euclidianas e aplicações; Euclidean distance geometry and applications
Fonte: Biblioteca Digital da Unicamp
Publicador: Biblioteca Digital da Unicamp
Tipo: Tese de Doutorado
Formato: application/pdf
Publicado em 23/01/2015
PT
Relevância na Pesquisa
76.24%
#Geometria de distâncias#Matrizes de distâncias euclidianas#Escalonamento multidimensional#Distance geometry#Euclidean distance matrices#Multidimensional scaling
Geometria de Distâncias Euclidianas (GDE) é o estudo da geometria euclidiana baseado no conceito de distância. É uma teoria útil em diversas aplicações, onde os dados consistem em um conjunto de distâncias e as possíveis soluções são pontos em algum espaço euclidiano que realizam as distâncias dadas. O problema chave em GDE é conhecido como Problema de Geometria de Distâncias (PGD), em que é dado um inteiro K>0 e um grafo simples, não direcionado, ponderado G=(V,E,d), cujas arestas são ponderadas por uma função não negativa d, e queremos determinar se existe uma função (realização) que leva os vértices de V em coordenadas no espaço euclidiano K-dimensional, satisfazendo todas as restrições de distâncias dadas por d. Consideramos tanto problemas teóricos quanto aplicações da GDE. Em termos teóricos, demonstramos a quantidade exata de soluções de uma classe de PGDs muito importante para problemas de conformação molecular e, além disso, conseguimos condições necessárias e suficientes para determinar quando um grafo completo associado a um PGD é realizável e qual o espaço euclidiano com dimensão mínima para tal realização. Em termos práticos, desenvolvemos um algoritmo que calcula tal realização em dimensão mínima com resultados superiores a um algoritmo clássico da literatura. Finalmente...
Link permanente para citações:
Euclidean distance matrices: special subsets, systems of coordinates and multibalanced matrices
Fonte: Sociedade Brasileira de Matemática Aplicada e Computacional
Publicador: Sociedade Brasileira de Matemática Aplicada e Computacional
Tipo: Artigo de Revista Científica
Formato: text/html
Publicado em 01/01/2007
EN
Relevância na Pesquisa
86.26%
In this paper we present special subsets of positive semidefinite matrices where the linear function k becomes a geometric similarity and its inverse can be easily computed. The images of these special subsets are characterized geometrically. We also study the systems of coordinates for spherical matrices and at the end, we introduce the class of multibalanced distance matrices.
Link permanente para citações:
On the eigenvalues of Euclidean distance matrices
Fonte: Sociedade Brasileira de Matemática Aplicada e Computacional
Publicador: Sociedade Brasileira de Matemática Aplicada e Computacional
Tipo: Artigo de Revista Científica
Formato: text/html
Publicado em 01/01/2008
EN
Relevância na Pesquisa
96.25%
In this paper, the notion of equitable partitions (EP) is used to study the eigenvalues of Euclidean distance matrices (EDMs). In particular, EP is used to obtain the characteristic polynomials of regular EDMs and non-spherical centrally symmetric EDMs. The paper also presents methods for constructing cospectral EDMs and EDMs with exactly three distinct eigenvalues.
Link permanente para citações:
On the Nonnegative Rank of Euclidean Distance Matrices
Fonte: PubMed
Publicador: PubMed
Tipo: Artigo de Revista Científica
EN
Relevância na Pesquisa
56%
The Euclidean distance matrix for n distinct points in ℝr is generically of rank r + 2. It is shown in this paper via a geometric argument that its nonnegative rank for the case r = 1 is generically n.
Link permanente para citações:
Positive semidefinite metric learning using boosting-like algorithms
Fonte: MIT Press
Publicador: MIT Press
Tipo: Artigo de Revista Científica
Publicado em //2012
EN
Relevância na Pesquisa
36.07%
#Mahalanobis distance#semidefinite programming#column generation#boosting#Lagrange duality#large margin nearest neighbor.
The success of many machine learning and pattern recognition methods relies heavily upon the identification of on an appropriate distance metric on the input data. It is often beneficial to learn such a metric from the input training data, instead of using a default one such as the Euclidean distance. In this work, we propose a boosting-based technique, termed BoostMetric, for learning a quadratic Mahalanobis distance metric. Learning a valid Mahalanobis distance metric requires enforcing the constraint that the matrix parameter to the metric remains positive semidefinite. Semidefinite programming is often used to enforce this constraint, but does not scale well and not easy to implement. BoostMetric is instead based on the observation that any positive semidefinite matrix can be decomposed into a linear combination of trace-one rank-one matrices. BoostMetric thus uses rank-one positive semidefinite matrices as weak learners within an efficient and scalable boosting-based learning process. The resulting methods are easy to implement, efficient, and can accommodate various types of constraints. We extend traditional boosting algorithms in that its weak learner is a positive semidefinite matrix with trace and rank being one rather than a classifier or regressor. Experiments on various datasets demonstrate that the proposed algorithms compare favorably to those state-of-the-art methods in terms of classification accuracy and running time.; Chunhua Shen...
Link permanente para citações:
Representing functional data in reproducing Kernel Hilbert spaces with applications to clustering, classification and time series problems
Fonte: Universidade Carlos III de Madrid
Publicador: Universidade Carlos III de Madrid
Tipo: info:eu-repo/semantics/doctoralThesis; info:eu-repo/semantics/doctoralThesis
Formato: application/octet-stream; application/octet-stream; application/pdf
ENG
Relevância na Pesquisa
36.27%
#Functional data analysis#Kernel Hilbert Spaces#Euclidean spaces#Time series#Análisis funcional#Espacios de Hilbert#Espacios euclídeos#Series temporales#Estadística
In modern data analysis areas such as Image Analysis, Chemometrics or Information Retrieval the raw data are often complex and their representation in Euclidean spaces is not straightforward. However most statistical data analysis techniques are designed to deal with points in Euclidean spaces and hence a representation of the data in some Euclidean coordinate system is always required as a previous step to apply multivariate analysis techniques. This process is crucial to guarantee the success of the data analysis methodologies and will be a core contribution of this thesis. In this work we will develop general data representation techniques in the framework of Functional Data Analysis (FDA) for classification and clustering problems. In Chapter 1 we motivate the problems to solve, describe the roadmap of the contributions and set up the notation of this work. In Chapter 2 we review some aspects concerning Reproducing Kernel Hilbert Spaces (RKHSs), Regularization Theory Integral Operators, Support Vector Machines and Kernel Combinations. In Chapter 3 we propose a new methodology to obtain finite-dimensional representations of functional data. The key idea is to consider each functional curve as a point in a general function space and then project these points onto a Reproducing Kernel Hilbert Space (RKHS) with the aid of Regularization theory. We will describe the projection methods...
Link permanente para citações:
Characterizing graphs with convex and connected configuration spaces
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36%
We define and study exact, efficient representations of realization spaces
Euclidean Distance Constraint Systems (EDCS), which includes Linkages and
Frameworks. Each representation corresponds to a choice of Cayley parameters
and yields a different parametrized configuration space. Significantly, we give
purely graph-theoretic, forbidden minor characterizations that capture (i) the
class of graphs that always admit efficient configuration spaces and (ii) the
possible choices of representation parameters that yield efficient
configuration spaces for a given graph. In addition, our results are tight: we
show counterexamples to obvious extensions. This is the first step in a
systematic and graded program of combinatorial characterizations of efficient
configuration spaces. We discuss several future theoretical and applied
research directions. Some of our proofs employ an unusual interplay of (a)
classical analytic results related to positive semi-definiteness of Euclidean
distance matrices, with (b) recent forbidden minor characterizations and
algorithms related to the notion of d-realizability of EDCS. We further
introduce a novel type of restricted edge contraction or reduction to a graph
minor, a "trick" that we anticipate will be useful in other situations.
Link permanente para citações:
Spectra of Euclidean Random Matrices
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 09/06/1999
Relevância na Pesquisa
45.91%
#Condensed Matter - Disordered Systems and Neural Networks#Condensed Matter - Statistical Mechanics#High Energy Physics - Theory
We study the spectrum of a random matrix, whose elements depend on the
Euclidean distance between points randomly distributed in space. This problem
is widely studied in the context of the Instantaneous Normal Modes of fluids
and is particularly relevant at the glass transition. We introduce a systematic
study of this problem through its representation by a field theory. In this way
we can easily construct a high density expansion, which can be resummed
producing an approximation to the spectrum similar to the Coherent Potential
Approximation for disordered systems.; Comment: 10 pages, 4 figures
Link permanente para citações:
On stochastic generation of ultrametrics in high-dimension Euclidean spaces
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.12%
The proof of the theorem, which states that the Euclidean metric on the set
of random points in an $n$-dimensional Euclidean space with the distribution of
a special class, converges in probability in the limit $n\rightarrow\infty$ to
the ultrametric is presented. The values of the ultrametric distance matrix is
completely determined by variances of point coordinates. Probabilistic
algorithm for the generation of finite ultrametric structures of any topology
in high-dimensional Euclidean space is presented. The validity of the algorithm
is demonstrated by explicit calculations of distance matrices with fixed
dimensions and ultrametricity indexes for various dimensions of Euclidean
space.; Comment: 13 pages, 2 figures
Link permanente para citações:
Distance matrices and isometric embeddings
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/10/2007
Relevância na Pesquisa
46.08%
We review the relations between distance matrices and isometric embeddings
and give simple proofs that distance matrices defined on euclidean and
spherical spaces have all eigenvalues except one non-negative. Several
generalizations are discussed.; Comment: 17 pages
Link permanente para citações:
Convex Optimization Learning of Faithful Euclidean Distance Representations in Nonlinear Dimensionality Reduction
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 22/06/2014
Relevância na Pesquisa
56.06%
Classical multidimensional scaling only works well when the noisy distances
observed in a high dimensional space can be faithfully represented by Euclidean
distances in a low dimensional space. Advanced models such as Maximum Variance
Unfolding (MVU) and Minimum Volume Embedding (MVE) use Semi-Definite
Programming (SDP) to reconstruct such faithful representations. While those SDP
models are capable of producing high quality configuration numerically, they
suffer two major drawbacks. One is that there exist no theoretically guaranteed
bounds on the quality of the configuration. The other is that they are slow in
computation when the data points are beyond moderate size. In this paper, we
propose a convex optimization model of Euclidean distance matrices. We
establish a non-asymptotic error bound for the random graph model with
sub-Gaussian noise, and prove that our model produces a matrix estimator of
high accuracy when the order of the uniform sample size is roughly the degree
of freedom of a low-rank matrix up to a logarithmic factor. Our results
partially explain why MVU and MVE often work well. Moreover, we develop a fast
inexact accelerated proximal gradient method. Numerical experiments show that
the model can produce configurations of high quality on large data points that
the SDP approach would struggle to cope with.; Comment: 44 pages...
Link permanente para citações:
Universal rigidity of bar frameworks in general position: a Euclidean distance matrix approach
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 14/01/2012
Relevância na Pesquisa
56.31%
A configuration p in r-dimensional Euclidean space is a finite collection of
labeled points p^1,p^2,...,p^n in R^r that affinely span R^r. Each
configuration p defines a Euclidean distance matrix D_p = (d_ij) =
(||p^i-p^j||^2), where ||.|| denotes the Euclidean norm. A fundamental problem
in distance geometry is to find out whether or not, a given proper subset of
the entries of D_p suffices to uniquely determine the entire matrix D_p. This
problem is known as the universal rigidity problem of bar frameworks. In this
chapter, we present a unified approach for the universal rigidity of bar
frameworks, based on Euclidean distance matrices (EDMs), or equivalently, on
projected Gram matrices. This approach makes the universal rigidity problem
amenable to semi-definite programming methodology. Using this approach, we
survey some recently obtained results and their proofs, emphasizing the case
where the points p^1,...,p^n are in general position.; Comment: To appear in "Distance geometry: with applications to molecular
conformation and sensor networks" edited by Mucherino et al. arXiv admin
note: text overlap with arXiv:1009.3318
Link permanente para citações:
Coordinate shadows of semi-definite and Euclidean distance matrices
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
56.1%
We consider the projected semi-definite and Euclidean distance cones onto a
subset of the matrix entries. These two sets are precisely the input data
defining feasible semi-definite and Euclidean distance completion problems. We
classify when these sets are closed, and use the boundary structure of these
two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. In
particular, we show that under a chordality assumption, the "minimal cones" of
these problems admit combinatorial characterizations. As a byproduct, we record
a striking relationship between the complexity of the general facial reduction
algorithm (singularity degree) and facial exposedness of conic images under a
linear mapping.; Comment: 21 pages
Link permanente para citações:
On the Geometric Interpretation of the Nonnegative Rank
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 04/09/2010
Relevância na Pesquisa
36.15%
The nonnegative rank of a nonnegative matrix is the minimum number of
nonnegative rank-one factors needed to reconstruct it exactly. The problem of
determining this rank and computing the corresponding nonnegative factors is
difficult; however it has many potential applications, e.g., in data mining,
graph theory and computational geometry. In particular, it can be used to
characterize the minimal size of any extended reformulation of a given
combinatorial optimization program. In this paper, we introduce and study a
related quantity, called the restricted nonnegative rank. We show that
computing this quantity is equivalent to a problem in polyhedral combinatorics,
and fully characterize its computational complexity. This in turn sheds new
light on the nonnegative rank problem, and in particular allows us to provide
new improved lower bounds based on its geometric interpretation. We apply these
results to slack matrices and linear Euclidean distance matrices and obtain
counter-examples to two conjectures of Beasly and Laffey, namely we show that
the nonnegative rank of linear Euclidean distance matrices is not necessarily
equal to their dimension, and that the rank of a matrix is not always greater
than the nonnegative rank of its square.
Link permanente para citações:
Counting real critical points of the distance to orthogonally invariant matrix sets
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
36.14%
Minimizing the Euclidean distance to a set arises frequently in applications.
When the set is algebraic, a measure of complexity of this optimization problem
is its number of critical points. In this paper we provide a general framework
to compute and count the real smooth critical points of a data matrix on an
orthogonally invariant set of matrices. The technique relies on "transfer
principles" that allow calculations to be done in the space of singular values
of the matrices in the orthogonally invariant set. The calculations often
simplify greatly and yield transparent formulas. We illustrate the method on
several examples, and compare our results to the recently introduced notion of
Euclidean distance degree of an algebraic variety.; Comment: 21 pages, 7 figures; a part of Section 5 in v1 became Appendix A
Link permanente para citações:
The Euclidean distance degree of an algebraic variety
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
46.13%
#Mathematics - Algebraic Geometry#Mathematics - Optimization and Control#51N35, 14N10, 14M12, 90C26, 13P25
The nearest point map of a real algebraic variety with respect to Euclidean
distance is an algebraic function. For instance, for varieties of low rank
matrices, the Eckart-Young Theorem states that this map is given by the
singular value decomposition. This article develops a theory of such nearest
point maps from the perspective of computational algebraic geometry. The
Euclidean distance degree of a variety is the number of critical points of the
squared distance to a generic point outside the variety. Focusing on varieties
seen in applications, we present numerous tools for exact computations.; Comment: to appear in Foundations of Computational Mathematics
Link permanente para citações:
Euclidean Distance Matrices: Essential Theory, Algorithms and Applications
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
66.19%
Euclidean distance matrices (EDM) are matrices of squared distances between
points. The definition is deceivingly simple: thanks to their many useful
properties they have found applications in psychometrics, crystallography,
machine learning, wireless sensor networks, acoustics, and more. Despite the
usefulness of EDMs, they seem to be insufficiently known in the signal
processing community. Our goal is to rectify this mishap in a concise tutorial.
We review the fundamental properties of EDMs, such as rank or
(non)definiteness. We show how various EDM properties can be used to design
algorithms for completing and denoising distance data. Along the way, we
demonstrate applications to microphone position calibration, ultrasound
tomography, room reconstruction from echoes and phase retrieval. By spelling
out the essential algorithms, we hope to fast-track the readers in applying
EDMs to their own problems. Matlab code for all the described algorithms, and
to generate the figures in the paper, is available online. Finally, we suggest
directions for further research.; Comment: - 17 pages, 12 figures, to appear in IEEE Signal Processing Magazine
- change of title in the last revision
Link permanente para citações:
On the Coherence Properties of Random Euclidean Distance Matrices
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Relevância na Pesquisa
66.1%
In the present paper we focus on the coherence properties of general random
Euclidean distance matrices, which are very closely related to the respective
matrix completion problem. This problem is of great interest in several
applications such as node localization in sensor networks with limited
connectivity. Our results can directly provide the sufficient conditions under
which an EDM can be successfully recovered with high probability from a limited
number of measurements.; Comment: 5 pages, SPAWC 2013
Link permanente para citações:
Riemannian Metric Learning for Symmetric Positive Definite Matrices
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 10/01/2015
Relevância na Pesquisa
36.27%
Over the past few years, symmetric positive definite (SPD) matrices have been
receiving considerable attention from computer vision community. Though various
distance measures have been proposed in the past for comparing SPD matrices,
the two most widely-used measures are affine-invariant distance and
log-Euclidean distance. This is because these two measures are true geodesic
distances induced by Riemannian geometry. In this work, we focus on the
log-Euclidean Riemannian geometry and propose a data-driven approach for
learning Riemannian metrics/geodesic distances for SPD matrices. We show that
the geodesic distance learned using the proposed approach performs better than
various existing distance measures when evaluated on face matching and
clustering tasks.
Link permanente para citações:
Conditionally Positive Functions and p-norm Distance Matrices
Fonte: Universidade Cornell
Publicador: Universidade Cornell
Tipo: Artigo de Revista Científica
Publicado em 12/06/2010
Relevância na Pesquisa
46.15%
In Micchelli's paper "Interpolation of scattered data: distance matrices and
conditionally positive functions", deep results were obtained concerning the
invertibility of matrices arising from radial basis function interpolation. In
particular, the Euclidean distance matrix was shown to be invertible for
distinct data. In this paper, we investigate the invertibility of distance
matrices generated by $p$-norms. In particular, we show that, for any $p\in (1,
2)$, and for distinct points $ x^1, ..., x^n \in {\cal R}^d $, where $n$ and
$d$ may be any positive integers, with the proviso that $ n \ge 2$, the matrix
$A \in {\cal R}^{n \times n} $ defined by $$ A_{ij} = \Vert x^i - x^j \Vert_p ,
\hbox{ for } 1 \le i, j \le n, $$ satisfies $$ (-1)^{n-1}\det A > 0 .$$ We also
show how to construct, for every $p > 2$, a configuration of distinct points in
some ${\cal R}^d$ giving a singular $p$-norm distance matrix. Thus radial basis
function interpolation using $p$-norms is uniquely determined by any distinct
data for $p \in (1,2]$, but not so for $p > 2$.
Link permanente para citações: