# Montanari's SNL-SDP algorithm

First of all, I would like to mention that I am new in CVX community. So, my doubt might be stupid. As I could not figure out the problem of my code, I have decided to post it here. I am trying to implement an algorithm as stated in the paper, titled as- Localization from Incomplete Noisy Distance Measurements, Javanmard and Montanari. In case, if the paper is not accessible, I am uploading a snapshot of the algorithm in my- Google Drive link.

A short description of the problem which I am facing, is described below.

I am dealing with a complete graph where each node represents a sensor. As it is a complete graph, each node knows the all the distance between it and any other node. Here, we have considered noiseless scenario, i.e., \bigtriangleup = 0.

The code written by me-

%% Calling CVX Package
%  E: Distance matrix
%  N: Number of sensor nodes
%  d: dimension where sensors are embedded
function [Q,X_est] = Montanari_Algo(E,N,d)
Q = zeros(N,N);
Mij = zeros(N,N);
cvx_precision best;
cvx_begin
variable Q(N,N) semidefinite                       % Defining variables
minimize(trace(Q))                                 % Objective function
subject to
% Constraints
for i = 1:N-1
for j = i:N
if E(i,j) ~= 0
Mij = Mij-Mij;
Mij(i,j) = -1;
Mij(j,i) = -1;
Mij(i,i) = 1;
Mij(j,j) = 1;
trace(Mij*Q) == square(E(i,j));
end
end
end
cvx_end
[U,S,~] = svd(Q);
X_est = (U(:,1:d)*sqrt(S(1:d,1:d)))';                 %Estimated sensor position
end


The input of the program will be E,N,d. Output will be X_{est}.

A sample input and expected output, I am providing-

X = -0.5+rand(2,10);
E = squareform(pdist(X'));
N = 10;
d = 2;


Expected output will be same as X, as we are dealing with complete graph in a noiseless scenario.

Looking forward for any generous help.

Your code is valid CVX code, and produces a solution. X_est does not equal X in your example.

1. Q = zeros(N,N); is ignored by CVX, but does no ham
2. I looked at the Google doc, but not the paper. I will have to defer to others as to whether X_est should equal X in this case, your claim not withstanding.

Yes. It is true that we may not be able to get back the exact X, but X_{est} should be as follows- X_{est}=OX+t, where O \in \mathbb{O}(d) and t \in \mathbb{R}^d (in this case, d=2). So after applying Arun’s algorithm (Least-Squares Fitting of Two 3-D Point Sets), if we calculate the error, then we should get back an error which tends to 0, but somehow I am not getting the correct result. My error is coming in the order of 10^{-1} which is completely wrong.

Thanks for your feedback.

Are there any cases for which you know that, (other than “roundoff” error, limited accuracy of SVD, solver tolerance, etc.) X should exactly equal X_est?

No. This algorithm is valid for anchor-less graph. In case of anchor-less graph, we can not expect exact recovery.

What are the ranges of the values of the inputs? Unless those are very small (to cause scaling issues) then I would suggest either your model formulation is wrong or the authors’ claims are wrong. In my experience CVX is rarely at fault in situations like this, with scaling issues being one exception. I would suggest that your next step should be to contact the authors of the paper.

It’s not clear to me why eigs would work where svd would not. After all, if you’re asking for a fixed number of singular values, you can always just compute the full decomposition and select the ones you want.