Montanari's SNL-SDP algorithm

1

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.

2

Here are comments, not an answer.

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

Comments:

  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.
3

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.

4

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?

5

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

6

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.

7

Thank you sir for your reply.

As you (@mcg) and Dr. @Mark_L_Stone pointed out, I changed the SVD part of the program by eigen decomposition using eigs, and now I am getting my desired result.

Thank you for your advice.

8

Ohh, eigs, the horror. eig is fine but I HATE the very unrerliable eigs, especially for non-interactive use in the middle of an algorithm (such as nonlinear optimization)… If SVD is applicable, I can’t think of any situation in which I would trust eigs over MATLAB’s svd. But if ti works for you, more power to you.

BTW, I never completed my Ph.D. thesis, but have recently resumed work on what I was trying to do 30+ years ago.

9

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.