Last stepsize smaller than minimum allowed.

[Yuanming Shi]

Hi,
I am using "conjugategradient" to solve the fixed rank problem. However, I often have the following errors.

iter cost val grad. norm
0 +7.4548517832343373e-07 1.22105297e-03
1 +2.6796472822356357e-07 7.32072030e-04
2 +2.6796472822352307e-07 7.32072030e-04
Last stepsize smaller than minimum allowed. See options.minstepsize.
Total time is 0.009164 [s] (excludes statsfun)
iter cost val grad. norm
0 +2.8085598946422683e-07 7.49474468e-04
Error using horzcat
Dimensions of matrices being concatenated are not consistent.

Error in fixedrankembeddedfactory/retraction (line 181)
[Ut, St, Vt] = svd([X.S+t*Z.M , t*Rv' ; t*Ru , zeros(k)]);

Error in linesearch_adaptive (line 65)
newx = problem.M.retr(x, d, alpha);

Error in conjugategradient (line 259)
[stepsize newx storedb lsmem lsstats] = options.linesearch(...


I guess the main reason is the the initial point is too good such that the cost is too small. Cloud you please help figure it? Thank you very much.

Best.

[Nicolas Boumal]

Hello,

Thank you for your question / possible bug report.

To me, it doesn't look like a situation where the initial point is too good to improve upon, because the gradient is not that small.

Could you show us the code for computing the cost and the gradient? Did you run checkgradient(problem); to make sure the gradient is correct?

Cheers,

Nicolas

[Yuanming Shi]

Hi,

  The cost and the gradient are given by as follows:

    problem.cost = @cost; 

    function f = cost(X)

        Xmat = X.U*X.S*X.V';

        f = .5*norm( P.*Xmat - A, 'fro')^2;

    end

    problem.egrad = @egrad;

    function G = egrad(X)

        Xmat = X.U*X.S*X.V';

        G = P.*Xmat - A;

    end

I indeed use chckgradient to make sure the gradient is correct. 

[Nicolas Boumal]

Hmm, this is puzzling. Could you show more of your code, please?

In particular, since the issue seems to come from matrix sizes, I'd like to make sure that the problem.M manifold is compatible with the size of A.

Could you also show how the initial guess is formed?

(If we can see the whole code, that's easiest).

Thanks,

Nicolas

[Yuanming Shi]

This is the code:

    %% Pick the manifold of matrices of size mxn of fixed rank k.

       problem.M = fixedrankembeddedfactory(K, K, r);

 

    %% Define the problem cost function f(X) = 1/2 * || P.*(X-A) ||^2

    problem.cost = @cost;  % The input X is a structure with fields U, S, V representing a rank k matrix as U*S*V'.

    function f = cost(X)

        Xmat = X.U*X.S*X.V';

        f = .5*norm( P.*Xmat - eye(K), 'fro')^2;

    end

 

    %% Define the Euclidean gradient of the cost function nabla f(X) = P.*(X-A)

    problem.egrad = @egrad;

    function G = egrad(X)

        % Same comment here about Xmat.

        Xmat = X.U*X.S*X.V';

        G = P.*Xmat - eye(K);

    end

    

      checkgradient(problem);

    [U, S, V] = svds(eye(K), r); X0.U = U; X0.S = S; X0.V = V;

 

    %% Notice that for this solver, the Hessian is not needed.

       [Xcg, xcost] = conjugategradient(problem, X0);

[Nicolas Boumal]

How do you produce the mask P?

Normally, the data matrix appearing in the cost and the gradient should be the masked matrix, so P.*eye(K) rather than just eye(K).

(also, eye(K) is a full rank matrix, so I don't necessarily expect algorithms to behave well; but admittedly, they should not create errors or abort early either ^_^).

Nicolas

[Yuanming Shi]

Here the mask P has a special structure such that the diagonal elements must be sampled. Actually, we always have P.A=eye(K) for any data matrix A. 

[Nicolas Boumal]

Ok.. I don't quite see what the problem means then. Nevertheless, I execute the following code, which has the structure I believe you are describing (A is identity, P is a mask with 1's on the diagonal); the checkgradient is OK.

I get no errors, but the algorithms get nowhere near convergence. They stop because of exceeded iteration count, but not because of minimum stepsize.

I'll need more input to help you out here. Are you using Manopt 1.0.7 (the latest available)?

Is there additional structure on the matrix you're trying to find, besides low rank? Is it symmetric, or symmetric positive semidefinite?

function foo()

    K = 200;

    r = 3;

    P = round(rand(K));

    P(1:(K+1):end) = 1;

    A = eye(K);

    PA = P.*A;

    %% Pick the manifold of matrices of size mxn of fixed rank k.

       problem.M = fixedrankembeddedfactory(K, K, r);

 

    %% Define the problem cost function f(X) = 1/2 * || P.*(X-A) ||^2

    problem.cost = @cost;  % The input X is a structure with fields U, S, V representing a rank k matrix as U*S*V'.

    function f = cost(X)

        Xmat = X.U*X.S*X.V';

        f = .5*norm( P.*Xmat - PA , 'fro')^2;

    end

 

    %% Define the Euclidean gradient of the cost function nabla f(X) = P.*(X-A)

    problem.egrad = @egrad;

    function G = egrad(X)

        % Same comment here about Xmat.

        Xmat = X.U*X.S*X.V';

        G = P.*Xmat - PA;

    end

    

      checkgradient(problem); pause;

    [U, S, V] = svds(eye(K), r); X0.U = U; X0.S = S; X0.V = V;

 

    %% Notice that for this solver, the Hessian is not needed.

    [Xcg, xcost] = conjugategradient(problem, X0);

    [Xcg, xcost] = trustregions(problem, X0);

end