function [err_msg,M,asym_dist,emb_metv,cpu_time]=MDS_Embed_Metric(D,d,cpu_limit)
% function [M,dist,err]=Embed_Metric_Partial_Chol(D,d,cpu_limit)
%
% Embeds the finite metric D into R^d using MDS method.
% Matlab code for MDS taken from R. Kimmel & N. Kiryati appears
% in Trans. on visualzation and comp. graphics vol.8 No. 2 Apr-Jun 2002
%
% Input:
%   D - the metric distances
%   d - dimension of the embedding space 
%   cpu_time - max cpu_time (ignored for now)
%
% Returns: err_msg- On success an empty string,
%                   otherwise, text explaining the error occured
%   M        - an n-by-d matrix of point coordinates
%   asym_dist- asymmetric distortion(max/min)
%   emb_metv - vector of embedding distances
%   cpu_time - the cpu time in seconds
error(nargchk(2,3,nargin));

[n,m]=size(D);
if n~=m
    err_msg= sprintf('Input not a square matrix: rows!=cols: %d!=%d\n',m,n);
else
    err_msg=[];
    tic;
    J=eye(n)-ones(n)./n;
    B=-.5*J*(D.^2)*J;
    if d > n
        warning(sprintf('Too large dimension= %d: setting to number of metric points %d',...
            d,n));
        d = n
    end
    [Q,L]= eigs(B,d,'LM');
    M=Q*(L.^(1/2));
    [asym_dist,emb_metv] = Metric_Distortion(D,M);
    cpu_time=toc;
end
if length(err_msg)
    M=[];
    asym_dist=[];
    emb_metv=[];
    cpu_time=[];
end