Distance Metric Learning not returning Positive Matrix I'm using the MATLAB code released by Eric P. Xing, related to their NIPS 2002 paper (pdf): "Distance metric learning, with application to clustering with side-information. Eric P. Xing, Andrew Y. Ng, Michael I. Jordan and Stuart Russell".
The code is available for download (.tar.gz) at this webpage.
When using the Newton-Rhapson method (Newton.m file), it is supposed to return a diagonal matrix, and when using the projections method (opt_sphere.m file), it is supposed to return a full matrix with entries greater than or equal to zero. Please see the paper for more on this.
However, when I try this on a sample dataset (Iris dataset), sometimes I get a matrix with negative entries when using the latter method. Similarly, with the former method, I sometimes get a matrix with two zero diagonals (that results in the transformed features being collapsed to a point).
Has anyone else experienced this before? Do you know what I am doing wrong?
As an example, consider the following code snippet (I have extracted the matlab code into the directory "code_metric_online"; these pairs of rows have the same labels, hence are similar: 30th and 42nd, 78th and 83rd, 9th and 49th; these pairs of rows have different labels, hence are dissimilar: 23rd and 61st, 96th and 150th, 45th and 80th):
addpath('code_metric_online/');
clear;
load fisheriris;

[N,d] = size(meas);
data = meas;
S = sparse(N, N);
D = sparse(N, N);

%S(9,49) = 1;
S(30,42) = 1;
S(78,83) = 1;

%D(45,80) = 1;
D(23,61) = 1;
D(96,150) = 1;

A = Newton(meas, S, D, 1);
A

%A = opt_sphere(meas, S, D, 100);
%A

transformed_data = data * (A^1/2)';
figure;
scatter(transformed_data(:, 1), transformed_data(:, 2));

The resulting matrix A in the above example will have two diagonal entries equal to zero, resulting in the plot being a single point. Similarly, if you comment out the Newton method and use opt_sphere instead, you will get a matrix A with negative elements.
If however, you add two new constraints (by un-commenting S(9,49) = 1; and D(45,80) = 1;, then the plot will be a straight line.
I cannot understand this strange behavior, while in the paper, it is clearly said that A is greater than or equal to zero.
 A: You mention:

Similarly, if you comment out the Newton method and use opt_sphere instead, you will get a matrix A with negative elements.

I'm not familiar with the referenced article and I've only taken a quick look at it, but it seems like the constraint on $A$ is $A \succcurlyeq 0$. This is used to denote the fact that $A$ is positive-semi definite, which is by all means not the same as saying that $A$ is a positive matrix (in that all its' entries are positive). For example, positive-semi definite matrices can have negative entries (unless they are on the diagonal).
Could this be the source for your confusion?
A: The reason why you see only a dot in the plot is because the dimensions you're plotting are actually the ones that contain the zeros you mention. The matrix A is 4x4, and the non-zero diagonal entries are in the third and fourth columns. If you use the corresponding columns from the matrix transformed_data you will see the correct data plotted.
Also, as @galoosh33 said, the opt_sphere returns a semi-definite matrix, so non-diagonal negatives are OK. If you would like to plot that out you could use 2 or 3 out of the 4 dimensions, or use PCA to further combine them:
c = [1,0,0;0,1,0;0,0,1];
scatter(transformed_data(:, 3), transformed_data(:, 4), ones(size(transformed_data,1),1)*30, c(id,:));

[~,score] = pca(transformed_data);
scatter3(score(:,1),score(:,2),score(:,3),ones(size(data,1),1)*30, c(id,:));

It is much later than the original post, so I guess the OP found a solution, but I hope this still helps somebody.
