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

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

#### 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).

#### 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).

#### 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).

### Examples

#### 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#### 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);

#### 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