A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The mathematical problem of approximating one matrix by another of lower rank is closely related to the fundamental postulate of factor-theory. When formulated as a least-squares problem, the normal equations cannot be immediately written down, since the elements of the approximate matrix are not independent of one another. The solution of the problem is simplified by first expressing the matrices in a canonic form. It is found that the problem always has a solution which is usually unique. Several conclusions can be drawn from the form of this solution. <s> BIB001 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Necessary and sufficient conditions are given for a set of numbers to be the mutual distances of a set of real points in Euclidean space, and matrices are found whose ranks determine the dimension of the smallest Euclidean space containing such points. Methods are indicated for determining the configuration of these points, and for approximating to them by points in a space of lower dimensionality. <s> BIB002 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Multidimensional scaling can be considered as involving three basic steps. In the first step, a scale of comparative distances between all pairs of stimuli is obtained. This scale is analogous to the scale of stimuli obtained in the traditional paired comparisons methods. In this scale, however, instead of locating each stimulus-object on a given continuum, the distances between each pair of stimuli are located on a distance continuum. As in paired comparisons, the procedures for obtaining a scale of comparative distances leave the true zero point undetermined. Hence, a comparative distance is not a distance in the usual sense of the term, but is a distance minus an unknown constant. The second step involves estimating this unknown constant. When the unknown constant is obtained, the comparative distances can be converted into absolute distances. In the third step, the dimensionality of the psychological space necessary to account for these absolute distances is determined, and the projections of stimuli on axes of this space are obtained. A set of analytical procedures was developed for each of the three steps given above, including a least-squares solution for obtaining comparative distances by the complete method of triads, two practical methods for estimating the additive constant, and an extension of Young and Householder's Euclidean model to include procedures for obtaining the projections of stimuli on axes from fallible absolute distances. <s> BIB003 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> 7. A. Kurosh, Ringtheoretische Probleme die mit dem Burnsideschen Problem uber periodische Gruppen in Zussammenhang stehen, Bull. Acad. Sei. URSS, Ser. Math. vol. 5 (1941) pp. 233-240. 8. J. Levitzki, On the radical of a general ring, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 462^66. 9. -, On three problems concerning nil rings, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 913-919. 10. -, On the structure of algebraic algebras and related rings, Trans. Amer. Math. Soc. vol. 74 (1953) pp. 384-409. <s> BIB004 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Multidimensional scaling is the problem of representingn objects geometrically byn points, so that the interpoint distances correspond in some sense to experimental dissimilarities between objects. In just what sense distances and dissimilarities should correspond has been left rather vague in most approaches, thus leaving these approaches logically incomplete. Our fundamental hypothesis is that dissimilarities and distances are monotonically related. We define a quantitative, intuitively satisfying measure of goodness of fit to this hypothesis. Our technique of multidimensional scaling is to compute that configuration of points which optimizes the goodness of fit. A practical computer program for doing the calculations is described in a companion paper. <s> BIB005 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> LetA1,A2, ...,An be anyn objects, such as variables, categories, people, social groups, ideas, physical objects, or any other. The empirical data to be analyzed are coefficients of similarity or distance within pairs (Ai,A i ), such as correlation coefficients, conditional probabilities or likelihoods, psychological choice or confusion, etc. It is desired to represent these data parsimoniously in a coordinate space, by calculatingm coordinates {x ia } for eachA i for a semi-metricd of preassigned formd ij =d(|xi1 -x j1 |, |xi2 -xj2|, ..., |x im -x jm |). The dimensionalitym is sought to be as small as possible, yet satisfy the monotonicity condition thatd ij <d kl whenever the observed data indicate thatA i is “closer” toA j thanA k is toA l . Minkowski and Euclidean spaces are special metric examples ofd. A general coefficient of monotonicityμ is defined, whose maximization is equivalent to optimal satisfaction of the monotonicity condition, and which allows various options both for treatment of ties and for weighting error-of-fit. A general rationale for algorithm construction is derived for maximizing μ by gradient-guided iterations; this provides a unified mathematical solution to the basic operational problems of norming the gradient to assure proper convergence, of trading between speed and robustness against undesired stationary values, and of a rational first approximation. Distinction is made between single-phase (quadratic) and two-phase (bilinear) strategies for algorithm construction, and between “hard-squeeze” and “soft-squeeze” tactics within these strategies. Special reference is made to the rank-image and related transformational principles, as executed by current Guttman-Lingoes families of computer programs. <s> BIB006 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> An algorithm for the analysis of multivariate data is presented along with some experimental results. The algorithm is based upon a point mapping of N L-dimensional vectors from the L-space to a lower-dimensional space such that the inherent data "structure" is approximately preserved. <s> BIB007 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> An individual differences model for multidimensional scaling is outlined in which individuals are assumed differentially to weight the several dimensions of a common “psychological space”. A corresponding method of analyzing similarities data is proposed, involving a generalization of “Eckart-Young analysis” to decomposition of three-way (or higher-way) tables. In the present case this decomposition is applied to a derived three-way table of scalar products between stimuli for individuals. This analysis yields a stimulus by dimensions coordinate matrix and a subjects by dimensions matrix of weights. This method is illustrated with data on auditory stimuli and on perception of nations. <s> BIB008 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> An algebraic examination of spatial models leads to the conclusion that a convenient description of the pattern of flows implicit in a geographical interaction table is obtained by displaying a field of vectors computed from the relative net exchanges. The vector field approximates the gradient of a scalar potential, and this may be invoked to explain the flows. The method can be applied to asymmetrical tables of a non-geographical nature. <s> BIB009 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> A new procedure is discussed which fits either the weighted or simple Euclidian model to data that may (a) be defined at either the nominal, ordinal, interval or ratio levels of measurement; (b) have missing observations; (c) be symmetric or asymmetric; (d) be conditional or unconditional; (e) be replicated or unreplicated; and (f) be continuous or discrete. Various special cases of the procedure include the most commonly used individual differences multidimensional scaling models, the familiar nonmetric multidimensional scaling model, and several other previously undiscussed variants. <s> BIB010 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The metric and dimensional assumptions that underlie the geometric representation of similarity are questioned on both theoretical and empirical grounds. A new set-theoretical approach to similarity is developed in which objects are represented as collections of features, and similarity is described as a feature-matching process. Specifically, a set of qualitative assumptions is shown to imply the contrast model, which expresses the similarity between objects as a linear combination of the measures of their common and distinctive features. Several predictions of the contrast model are tested in studies of similarity with both semantic and perceptual stimuli. The model is used to uncover, analyze, and explain a variety of empirical phenomena such as the role of common and distinctive features, the relations between judgments of similarity and difference, the presence of asymmetric similarities, and the effects of context on judgments of similarity. The contrast model generalizes standard representations of similarity data in terms of clusters and trees. It is also used to analyze the relations of prototypicality and family resemblance <s> BIB011 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Any event in the history of the organism is, in a sense, unique. Consequently, recognition, learning, and judgment presuppose an ability to categorize stimuli and classify situations by similarity . As Quine (1969) puts it: "There is nothing more basic to thought and language than our sense of similarity ; our sorting of things into kinds [p . 1161 ." Indeed, the notion of similarity that appears under such different names as proximity, resemblance, communality, representativeness, and psychological distance is fundamental to theories of perception, learning, and judgment . This chapter outlines a new theoretical analysis of similarity and investigates some of its empirical consequences . The theoretical analysis of similarity relations has been dominated by geometric models. Such models represent each object as a point in some coordinate space so that the metric distances between the points reflect the observed similarities between the respective objects . In general, the space is assumed to be Euclidean, and the purpose of the analysis is to embed the objects in a space of minimum dimensionality on the basis of the observed similarities, see Shepard (1974) . In a recent paper (Tversky, 1977), the first author challenged the dimensionalmetric assumptions that underlie the geometric approach to similarity and developed an alternative feature-theoretical approach to the analysis of similarity relations. In this approach, each object a is characterized by a set of features, denoted A, and the observed similarity of a to b, denoted s(a, b), is expressed as a function of their common and distinctive features (see Fig . 4.1) . That is, the observed similarity s(a, b) is expressed as a function of three arguments : A f1B, the features shared by a and b ;A B, the features of a that are not shared by b ; B A, the features of b that are not shared by a . Thus the similarity between <s> BIB012 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> A new procedure is discussed which represents the asymmetric relationships between N objects. These relationships must be defined at the interval levels of measurement in Steven’s terminology. This method not only reveals the clustering of the objects but also enables us to give information about both the magnitude and the orientation of the “skewness” between objects in “a” configuration. The procedure optimizes the fit of the model directly to the data by an alternating least squares procedure. It is found to be robust, as the Hessian Matrix of the loss function is positive definite at least in two dimensional case, except for a special case. The method is illustrated with an artificial data and three empirical data. <s> BIB013 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> A single-step maximum likelihood estimation procedure is developed for multidimensional scaling of dissimilarity data measured on rating scales. The procedure can fit the euclidian distance model to the data under various assumptions about category widths and under two distributional assumptions. The scoring algorithm for parameter estimation has been developed and implemented in the form of a computer program. Practical uses of the method are demonstrated with an emphasis on various advantages of the method as a statistical procedure. <s> BIB014 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Statistical problems associated with multidimensional scaling are reviewed. Indices of similarity or dissimilarity have been fitted by two classes of models: point representation using a distance measure and vector representation using an inner product. In addition to these parameters representing stimulus-attribute relations, it is usual to require some subject-specific parameters to model idiosyncracies in response patterns and variance components. Techniques for coping with nuisance parameters and deriving interval estimates are discussed in the context of maximum likelihood estimation. Some generalizations to multivariate situations are also developed. <s> BIB015 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Restricted multidimensional scaling models [Bentler & Weeks, 1978] allowing constraints on parameters, are extended to the case of asymmetric data. Separate functions are used to model the symmetric and antisymmetric parts of the data. The approach is also extended to the case in which data are presumed to be linearly related to squared distances. Examples of several models are provided, using journal citation data. Possible extensions of the models are considered. <s> BIB016 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> This paper proposes a model to analyze the structure and context effects involved in dissimilarity judgment. With some restrictions incorporated, the model is also interpreted as a kind of the distance-density model and further interpreted as a mixed distance and content model. Algorithms for multidimensional scaling based on the proposed model are implemented using nonlinear optimization methods. The algorithms are evaluated through a Monte Carlo study, and applications are demonstrated with real data. Problems regarding the model, the algorithms and possible applications are discussed. <s> BIB017 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Nonmetric multidimensional scaling which could be applied to a square asymmetric inter-stimulus proximity matrix is presented. In the model each stimulus is represented as a point and a circle (sphere, hypersphere) whose center is at that point in a multidimensional Euclidean space. The radius of a circle (sphere, hypersphere) tells the skew-symmetry of the corresponding stimulus. In a sense the model is a nonmetric generalization of Weeks and Bentler (1982) ’s model. An algorithm to derive the coordinates of points and radii of circles (spheres, hypers-pheres) which minimize the discrepancy of the coordinates and radii from the monotone relationship with given interstimulus proximities is described. An application to car switching data among 16 car segments is represented. <s> BIB018 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The recent history of multidimensional data analysis suggests two distinct traditions that have developed along quite different lines. In multidimensional scaling (MDS), the available data typically describe the relationships among a set of objects in terms of similarity/dissimilarity (or (pseudo-)distances). In multivariate analysis (MVA), data usually result from observation on a collection of variables over a common set of objects. This paper starts from a very general multidimensional scaling task, defined on distances between objects derived from one or more sets of multivariate data. Particular special cases of the general problem, following familiar notions from MVA, will be discussed that encompass a variety of analysis techniques, including the possible use of optimal variable transformation. Throughout, it will be noted how certain data analysis approaches are equivalent to familiar MVA solutions when particular problem specifications are combined with particular distance approximations. <s> BIB019 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> A common need in machine vision is to compute the 3-D rigid body transformation that aligns two sets of points for which correspondence is known. A comparative analysis is presented here of four popular and efficient algorithms, each of which computes the translational and rotational components of the transform in closed form, as the solution to a least squares formulation of the problem. They differ in terms of the transformation representation used and the mathematical derivation of the solution, using respectively singular value decomposition or eigensystem computation based on the standard \([ \vec{R}, \vec{T} ]\) representation, and the eigensystem analysis of matrices derived from unit and dual quaternion forms of the transform. This comparison presents both qualitative and quantitative results of several experiments designed to determine (1) the accuracy and robustness of each algorithm in the presence of different levels of noise, (2) the stability with respect to degenerate data sets, and (3) relative computation time of each approach under different conditions. The results indicate that under “ideal” data conditions (no noise) certain distinctions in accuracy and stability can be seen. But for “typical, real-world” noise levels, there is no difference in the robustness of the final solutions (contrary to certain previously published results). Efficiency, in terms of execution time, is found to be highly dependent on the computer system setup. <s> BIB020 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Principal component analysis (PCA) is a commonly applied technique for dimensionality reduction. PCA implicitly minimizes a squared loss function, which may be inappropriate for data that is not real-valued, such as binary-valued data. This paper draws on ideas from the Exponential family, Generalized linear models, and Bregman distances, to give a generalization of PCA to loss functions that we argue are better suited to other data types. We describe algorithms for minimizing the loss functions, and give examples on simulated data. <s> BIB021 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Fundamentals of MDS.- The Four Purposes of Multidimensional Scaling.- Constructing MDS Representations.- MDS Models and Measures of Fit.- Three Applications of MDS.- MDS and Facet Theory.- How to Obtain Proximities.- MDS Models and Solving MDS Problems.- Matrix Algebra for MDS.- A Majorization Algorithm for Solving MDS.- Metric and Nonmetric MDS.- Confirmatory MDS.- MDS Fit Measures, Their Relations, and Some Algorithms.- Classical Scaling.- Special Solutions, Degeneracies, and Local Minima.- Unfolding.- Unfolding.- Avoiding Trivial Solutions in Unfolding.- Special Unfolding Models.- MDS Geometry as a Substantive Model.- MDS as a Psychological Model.- Scalar Products and Euclidean Distances.- Euclidean Embeddings.- MDS and Related Methods.- Procrustes Procedures.- Three-Way Procrustean Models.- Three-Way MDS Models.- Modeling Asymmetric Data.- Methods Related to MDS. <s> BIB022 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> It is often useful to know the geographic positions of nodes in a communications network, but adding GPS receivers or other sophisticated sensors to every node can be expensive. We present an algorithm that uses connectivity information who is within communications range of whom to derive the locations of the nodes in the network. The method can take advantage of additional information, such as estimated distances between neighbors or known positions for certain anchor nodes, if it is available. The algorithm is based on multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n nodes. Through simulation studies, we demonstrate that the algorithm is more robust to measurement error than previous proposals, especially when nodes are positioned relatively uniformly throughout the plane. Furthermore, it can achieve comparable results using many fewer anchor nodes than previous methods, and even yields relative coordinates when no anchor nodes are available. <s> BIB023 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> One of the most popular graph drawing methods is based on achieving graph-theoretic target distances. This method was used by Kamada and Kawai [15], who formulated it as an energy optimization problem. Their energy is known in the multidimensional scaling (MDS) community as the stress function. In this work, we show how to draw graphs by stress majorization, adapting a technique known in the MDS community for more than two decades. It appears that majorization has advantages over the technique of Kamada and Kawai in running time and stability. We also found the majorization-based optimization being essential to a few extensions to the basic energy model. These extensions can improve layout quality and computation speed in practice. <s> BIB024 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> An efficient algorithm for isometry-invariant matching of surfaces is presented. The key idea is computing the minimum-distortion mapping between two surfaces. For this purpose, we introduce the generalized multidimensional scaling, a computationally efficient continuous optimization algorithm for finding the least distortion embedding of one surface into another. The generalized multidimensional scaling algorithm allows for both full and partial surface matching. As an example, it is applied to the problem of expression-invariant three-dimensional face recognition. <s> BIB025 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently.The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution.We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods.The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations.Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected. <s> BIB026 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> We present an efficient computational framework for isometry-invariant comparison of smooth surfaces. We formulate the Gromov-Hausdorff distance as a multidimensional scaling-like continuous optimization problem. In order to construct an efficient optimization scheme, we develop a numerical tool for interpolating geodesic distances on a sampled surface from precomputed geodesic distances between the samples. For isometry-invariant comparison of surfaces in the case of partially missing data, we present the partial embedding distance, which is computed using a similar scheme. The main idea is finding a minimum-distortion mapping from one surface to another, while considering only relevant geodesic distances. We discuss numerical implementation issues and present experimental results that demonstrate its accuracy and efficiency. <s> BIB027 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Compounds useful as complementary DNA (cDNA) include deoxyribonucleotides and at least one ribonucleotide. They may be depicted by the general formula: wherein (dN)a and (dN)c represent series of deoxyribonucleotides and (rN)b represents a series of ribonucleotides; wherein a, b, and c are the number of nucleotides in the series, with the proviso that b is >/=1, a is >/=35, and c is >/=10; wherein the series of deoxyribonucleotides (dN)a includes a series of deoxyribonucleotides which is substantially complementary to the series of deoxyribonucleotides (dN)c and the dashed line represents noncovalent bonding between the complementary deoxyribonucleotide series; and wherein the solid line represents a covalent phosphodiester bond. These compounds may be prepared from messenger RNA (mRNA) containing the genetic information necessary for cellular production of desired products such as polypeptides. After appropriate modification, they may be combined with DNA from a suitable cloning vehicle such as a plasmid and the resulting combined DNA used to transform bacterial cells. The transformed bacterial cells may then be grown and harvested; and the desired product or products recovered. <s> BIB028 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> A maximum likelihood estimation method is proposed to fit an asymmetric multidimensional scaling model to a set of asymmetric data. This method is based on successive categories scaling, and enables us to analyze asymmetric proximity data measured, at least, at an ordinal scale level. It enables us to examine not only the appropriate scaling level of the data, but also the appropriate dimensionality of the model, using AIC. Prior to or in fitting the asymmetric MDS model, it is important to verify that the data are sufficiently asymmetric. Some variants of symmetry hypotheses are developed for this purpose. Since the emphasis in our paper is not on hypothesis testing, but on model diagnosis, we compare several candidate models including models with these hypotheses based on a similar model comparison idea using AIC. The method is applied to artificial data and a set of friendship data among nations in East Asia and the USA. Relations to other methods are also discussed. <s> BIB029 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The advent of multiple-point geostatistics (MPS) gave rise to the integration of complex subsurface geological structures and features into the model by the concept of training images. Initial algorithms generate geologically realistic realizations by using these training images to obtain conditional probabilities needed in a stochastic simulation framework. More recent pattern-based geostatistical algorithms attempt to improve the accuracy of the training image pattern reproduction. In these approaches, the training image is used to construct a pattern database. Consequently, sequential simulation will be carried out by selecting a pattern from the database and pasting it onto the simulation grid. One of the shortcomings of the present algorithms is the lack of a unifying framework for classifying and modeling the patterns from the training image. In this paper, an entirely different approach will be taken toward geostatistical modeling. A novel, principled and unified technique for pattern analysis and generation that ensures computational efficiency and enables a straightforward incorporation of domain knowledge will be presented. <s> BIB030 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> This book introduces MDS as a psychological model and as a data analysis technique for the applied researcher. It also discusses, in detail, how to use two MDS programs, Proxscal (a module of SPSS) and Smacof (an R-package). The book is unique in its orientation on the applied researcher, whose primary interest is in using MDS as a tool to build substantive theories. This is done by emphasizing practical issues (such as evaluating model fit), by presenting ways to enforce theoretical expectations on the MDS solution, and by discussing typical mistakes that MDS users tend to make. The primary audience of this book are psychologists, social scientists, and market researchers. No particular background knowledge is required, beyond a basic knowledge of statistics. <s> BIB031 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The concept of similarity, or a sense of 'sameness' among things, is pivotal to theories in the cognitive sciences and beyond. Similarity, however, is a difficult thing to measure. Multidimensional scaling (MDS) is a tool by which researchers can obtain quantitative estimates of similarity among groups of items. More formally, MDS refers to a set of statistical techniques that are used to reduce the complexity of a data set, permitting visual appreciation of the underlying relational structures contained therein. The current paper provides an overview of MDS. We discuss key aspects of performing this technique, such as methods that can be used to collect similarity estimates, analytic techniques for treating proximity data, and various concerns regarding interpretation of the MDS output. MDS analyses of two novel data sets are also included, highlighting in step-by-step fashion how MDS is performed, and key issues that may arise during analysis. WIREs Cogn Sci 2013, 4:93-103. doi: 10.1002/wcs.1203 This article is categorized under: Psychology > Perception and Psychophysics. <s> BIB032 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> The ability to understand natural language text is far from being emulated in machines. One of the main hurdles to overcome is that computers lack both the common and common-sense knowledge that humans normally acquire during the formative years of their lives. To really understand natural language, a machine should be able to comprehend this type of knowledge, rather than merely relying on the valence of keywords and word co-occurrence frequencies. In this article, the largest existing taxonomy of common knowledge is blended with a natural-language-based semantic network of common-sense knowledge. Multidimensional scaling is applied on the resulting knowledge base for open-domain opinion mining and sentiment analysis. <s> BIB033 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> Multidimensional Scaling (MDS) is a classic technique that seeks vectorial representations for data points, given the pairwise distances between them. However, in recent years, data are usually collected from diverse sources or have multiple heterogeneous representations. How to do multidimensional scaling on multiple input distance matrices is still unsolved to our best knowledge. In this paper, we first define this new task formally. Then, we propose a new algorithm called Multi-View Multidimensional Scaling (MVMDS) by considering each input distance matrix as one view. Our algorithm is able to learn the weights of views (i.e., distance matrices) automatically by exploring the consensus information and complementary nature of views. Experimental results on synthetic as well as real datasets demonstrate the effectiveness of MVMDS. We hope that our work encourages a wider consideration in many domains where MDS is needed. <s> BIB034 </s> A State-of-the-Art Survey on Multidimensional Scaling-Based Localization Techniques <s> A. What Is MDS? <s> This survey presents multidimensional scaling (MDS) methods and their applications in real world. MDS is an exploratory and multivariate data analysis technique becoming more and more popular. MDS is one of the multivariate data analysis techniques, which tries to represent the higher dimensional data into lower space. The input data for MDS analysis is measured by the dissimilarity or similarity of the objects under observation. Once the MDS technique is applied to the measured dissimilarity or similarity, MDS results in a spatial map. In the spatial map, the dissimilar objects are far apart while objects which are similar are placed close to each other. In this survey article, MDS is described in comprehensive fashion by explaining the basic notions of classical MDS and how MDS can be helpful to analyze the multidimensional data. Later on, various special models based on MDS are described in a more mathematical way followed by comparisons of various MDS techniques. <s> BIB035
MDS is a dimensionality reduction method which converts a higher dimensional data into a lower dimension. Due to this dimensionality reduction provided by MDS, it can display the data graphically which is more meaningful and easy to understand. There is a large number of dimensionality reduction methods such as factor analysis, principal component analysis, and Isomap. But due to the simplicity and wide range of applications, MDS is most popular. The input for any MDS based method is a dissimilarity or similarity information among the objects or points BIB022 , BIB025 , BIB004 . The MDS method uses this dissimilarity or similarity information and tries to closely match it to the Euclidian distance between those objects or points BIB030 BIB033 BIB034 BIB024 . Unlike factor analysis, MDS does not depend on the assumptions of linearity and normality BIB026 . The only assumption required for MDS is that the number of dimensions required should be one less than the number of points BIB027 . Since MDS is one of the classical data analysis methods used in wide range of applications, therefore, rich literature exists on MDS methods for achieving data visualization and data analysis BIB031 BIB032 BIB035 . Results on classical MDS and its recent variants are briefly discussed in BIB022 ,  . The MDS method was originated by Eckart and Young BIB001 , BIB002 , while the first input metric for MDS was developed by Torgerson BIB003 . In  , BIB021 the authors established a relationship between MDS and principal component analysis. The non-metric MDS was developed by Kruskal in BIB005 where the dissimilarity or similarity information relates monotonically to the Euclidian distances  . Table I shows the development of MDS methods over the years. Every MDS method can be specified by its loss function BIB007 and a number of different loss functions have been developed for MDS methods. Some of the famous loss functions for MDS are Coombs unfolding model  , individual difference model BIB008 , ALSCAL BIB010 , maximum likelihood BIB015 , and optimal scaling BIB019 . Table II summarizes different loss models used for MDS methods. The loss functions basically relates the measured values (dissimilarities) to their Euclidean distances. To elaborate more, consider that the dissimilarity between any two points i and j is ρ ij and their corresponding Euclidean distance is d ij , then the squared error function is represented as Based on the squared error function, the total error (raw Stress) for all pair of objects is obtained as where n is the total number of objects. The major problem with the above raw stress function is that it is invariant under coordinate scaling transformation. Hence, normalization techniques are used to address the problem of in-variance. One of the most proper choice for the normalization is using the dissimilarity, i.e., ρ ij . By using ρ ij as a normalization parameter yields the well-known loss function for MDS called Kruskal stress function which is given as This loss function can be solved by using the well-known iterative majorization approach called scaling by majorizing of a complicated function (SMACOF). To further elaborate, we consider a simple example of various sports classification. The range of dissimilarities is set to 1 = very similar, 3 = average similarity, and 5 = non-similar, respectively. We consider five different sports which include cricket, baseball, hockey, football, and golf. The dissimilarity matrix between these sports is given in Table III . Applying classical MDS to this dissimilarity matrix yields a graphical map (Fig. 2 ) of these sports which shows the relationship between these sports in a two-dimensional space. For example, Fig. 2 shows graphically that cricket and baseball are similar sports, similarly, hockey and football are similar while golf is different than all the other sports. Note that this MDS map has no real orientation which means that it can be rotated around its center. The main characteristics are the relative positions of each point. Traditional MDS methods consider that distances among objects are symmetric, although this consideration is not always satisfied. For instance, BIB011 and BIB012 explained the characters of similarity among objects studied with psychological scale and concluded that cognitive similarity is mostly asymmetric. The motivation behind these asymmetric MDS methods is to remove the shortcomings of traditional MDS methods, i.e., in case where similarity or dissimilarity matrices are asymmetric in nature as they are based on the supposition that similarity or dissimilarity matrices can be associated with inter-point distances in a given metric space BIB003 , BIB005 , BIB006 . Many researchers have extended the traditional MDS methods by assuming that the similarity or dissimilarity among objects is not a function of only inter-point distances but is also a function of the quantities associated with these objects. For instance, the squared distances are extended by weights in weighted distance model which was first proposed by  . In  , BIB017 and BIB016 the authors have proposed altered distance models where the distance between points is established by a few constants associated with these points. In  and BIB018 a nonmetric type of generalized altered distance model is proposed. Smallest space analysis-2 (SSA-2) is introduced in BIB006 and  , where column and row compatibility is applied on the data to get two solutions in metric space. Wind model is proposed in BIB009 , where the asymmetries are explained by the direction of wind given to mesh point on the arrangement of objects. In  and  the authors proposed a model, in which the asymmetries are analyzed by utilizing the Randers metric, i.e., an asymmetric metric function. In BIB011 the authors proposed the feature matching model which explains the similarity or dissimilarity among two objects through a linear combination of the amount of distinctive and common characteristic of the two objects. In BIB013 and  the authors proposed a model using a generalization of scalar products, which fits the magnitude of cross and inner (scalar) products of solution vectors to skew-symmetric and symmetric parts of the data, respectively. References  and  , split the asymmetric proximity matrix into two components, i.e., symmetric and skew-symmetric components and then deal with them separately. For symmetric component, traditional MDS method is used, while for skew-symmetric component canonical decomposition is used. In BIB029 the authors proposed a maximum likelihood method for asymmetric proximity matrix, which expands the work for asymmetrical data BIB014 . MDS maps the original high dimensional data (m dimensions) in to a lower dimensional data (d dimensions). It addresses the problem of constructing a configuration between the n points from n × n matrix D, which is called distance affinity matrix and it is symmetric, i.e., d ii = 0, and d ij > 0, i = j . MDS finds n data points P = {p i = {x i , y i }, . . . , p n = {x n , y n }} from the distance matrix D in a d dimensional space, such that the estimated distancê d ij between p i and p j , matches the Eucleadian distance as closely as possible. In BIB028 , [157] , the loss function for MDS is considered as which is highly nonlinear. To solve it, the distance affinity matrix D is first converted to a kernel matrix of inner product P T P by where H = I − 1 n ee T is called the double centering operation, I is identity matrix of size n × n, and e is a column vector of 1's. The solution of (6) is Y = Λ 1/2 V T where V are the eigen-vectors of P T P in d dimensions and Λ are the d eigenvalues of P T P. In recent past MDS is widely is used for simultaneous localization and mapping of WSNs and IoT networks. In BIB023 a proximity information based sensor network localization is proposed. The main idea in BIB023 is to construct a local configuration of sensor nodes using classical MDS (CMDS). The analogy between object distances and node distances in a network is used for the purpose of WSNs-IoT localization. MDS algorithm uses inter-node distances in order to produce two or three-dimensional representation, which corresponds to the real nodes deployment. Since nodes are capable to measure the inter-node distances with respect to their neighboring nodes, the only problem remains to obtain the non-neighboring inter-node distances. In MDS method, these distances are approximated by using Floyd Warshall shortest path algorithm  . Distances between every node in the network are collected at the central station. The remaining (non-neighboring) distances are calculated by the central station. The calculation for 2D network consists of the following steps: • Compute the shortest path distances between every node in the network (using either Dijkstra or Floyd algorithm). These shortest path distances work as an input data for MDS. • Classical MDS is applied to the shortest path distance matrix which results in the spectral decomposition of input data matrix. The two largest eigenvalues and the corresponding eigen-vectors form the relative location of every node in the network (three largest Eigenvalues and eigen-vectors for 3D localization). • Finally, the relative locations are transformed to the absolute global locations by using the anchor nodes. This transformation includes optimal rotation, translation, and reflection. This type of transformation is also called rigid or Euclidean transformation BIB020 . Based on the computation, MDS based localization methods have been proposed in the past which can be categorized into centralized, semi-centralized, and distributed methods.