# 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); #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*sol-P);
expand(sol*sol-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); #verification: the completion has rank 2