NewtonSLRA: Installation, documentation and examples

1. Installation

   Download the archive NewtonSLRA.tar.gz and uncompress it. The following commands load the library in Maple

   libname:=LIBDIR_PATH, libname;
   with(NewtonSLRA);

   where LIBDIR_PATH is the path to the directory containing NewtonSLRA.mla and NewtonSLRA.hdb.

2. Usage

   The library provides three functions: NSLRA, ApproximateGCD, and MatrixCompletion. To get more details on the computations, use

   infolevel[FUNCTION_NAME]:=1;

   before calling the function.

   1. NSLRA

      This is the most general function for Structured Low-Rank Approximation provided in the package. Given a linear space E of matrices, an input matrix M0 and a target rank r, it returns (if it converges) a nearby matrix M of rank r such that M-M0 is in E.

      Usage: NSLRA(M0,E,r,eps,nbitmax)
      Returns M, dist, it

      • M0: matrix whose entries are floating-point numbers.
      • E: an orthonormal basis of the linear space for the Frobenius scalar product (<M1,M2>=Trace(M1.Transpose(M2))).
      • r: integer, target rank.
      • eps: convergence criterion, the algorithm stops when the size of the step during one iteration is less than eps (for the Frobenius distance).
      • nbitmax: integer, maximal number of iterations. The algorithm stops if convergence has not been reached before this number of iterations.
      • M: the low-rank approximation of M0 (if the iteration has converged).
      • dist: Frobenius distance between M and M0.
      • it: number of iterations performed by the algorithm (if it=nbitmax, then it has not converged).

   2. ApproximateGCD

      This function computes an approximate GCD of degree d of two univariate polynomials P and Q, i.e. three univariate polynomials G, A and B such that degree(G) is d and the pair (G*A, G*B) is near the pair (P,Q) for the 2-norm.

      Usage: ApproximateGCD(P,Q,d,eps,nbitmax)
      Returns G, A, B, dist, it.

      • P: polynomial with indeterminate x and floating-point coefficients.
      • Q: polynomial with indeterminate x and floating-point coefficients.
      • d: integer, target degree of the approximate GCD.
      • eps: convergence criterion, the algorithm stops when the size of the step during one iteration is less than eps (for the Frobenius distance).
      • nbitmax: integer, maximal number of iterations. The algorithm stops if convergence has not been reached before this number of iterations.
      • G: approximate GCD.
      • A: approximate cofactor of P.
      • B: approximate cofactor of Q.
      • dist: 2-norm of (P-G*A,Q-G*B).
      • it: number of iterations performed by the algorithm (if it=nbitmax, then it has not converged).

   3. MatrixCompletion

      Given a target rank r, a matrix M whose entries are floating-point numbers, and a list of pairs of integers, the function outputs a nearby matrix N of rank at most r which has exactly the same entries as M at the coordinates given by the pairs of integers.

      Usage: MatrixCompletion(M, r, samples_pos, eps, nbitmax)
      Returns N, dist, it.

      • M: input matrix whose entries are either floating-point numbers or distinct variables.
      • r: integer, target rank.
      • samples_pos: sequence of pairs of indices indicating the position of the fixed entries in the matrix.
      • nbitmax: integer, maximal number of iterations. The algorithm stops if convergence has not been reached before this number of iterations.
      • N: completed matrix.
      • dist: Frobenius distance between N and the evaluation of M at the starting values.
      • it: number of iterations performed by the algorithm (if it=nbitmax, then it has not converged).

3. Examples

   1. NSLRA: structured low-rank approximation of a 3*3 Hankel matrix.

      with(NewtonSLRA): with(LinearAlgebra):
      E:=[seq(HankelMatrix([seq(0,j=1..i-1), evalf(1/sqrt(3-abs(3-i))),seq(0,j=i+1..5)]),i=1..5)];
      #E is an orthonormal basis of the linear space of 3*3 Hankel matrices
      M0:=HankelMatrix([1.5,2,3,4,5]);
      Rank(M0); #M0 has rank 3
      sol:=NSLRA(M0,E,2,0.00001,50); #finds a rank 2 Hankel approximation of M0 in 2 iterations
      Rank(sol[1]); #verification: the solution is indeed a rank 2 matrix

   2. Approximate GCD

      with(NewtonSLRA);
      P:=x^2+5*x+6;
      Q:=expand((x+3)*(x-1)+0.3+0.2*x);
      gcd(P,Q); #Maple finds that these polynomials are coprime
      sol:=ApproximateGCD(P,Q,1,0.000001,50);
      #Computes an approximate GCD of degree 1 in 4 iterations
      expand(sol[1]*sol[2]-P);
      expand(sol[1]*sol[3]-Q);
      

   3. Matrix completion: rank 2 completion of a 3*3 matrix

      with(NewtonSLRA): with(LinearAlgebra):
      M:=Matrix(3,3,[0,15.4,90.7,-31.3,0,-75.1,56.8,2.4,0]);
      sol:=MatrixCompletion(M,2,[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]],0.0001,50);
      Rank(sol[1]); #verification: the completion has rank 2