Caratheodory-Tchakalo Least Squares

Caratheodory-Tchakalo Least Squares

Federico Piazzon, Alvise Sommariva and Marco Vianello

Dip. Matematica Tullio Levi-Civita Univ. Padova fpiazzon@.math.unipd.it

DRWA17, Dolomites Research Week on Approximation 2017, Alba di Canazei September 3-8th 2017

Abstract

We discuss the Caratheodory-Tchakalo (CATCH) subsampling method, implemented by Linear or Quadratic Programming, for the compression of multivariate discrete measures and polynomial Least Squares

Discrete Tchakaloff Theorem

Theorem: Let µ be a positive nite measure with compact support in R ^d . Denote by P ⁿ the space of (the traces on the support of µ of) the algebraic polynomials of total degree not larger than n. There exist m ≤ N := dim P ⁿ , x ¹ , . . . , x _m ∈ supp µ and (w ¹ , . . . , w _m ) ∈ (R ⁺ ) ^m such that

Z

pdµ =

m

X

i=1

p(x _i )w _i , ∀p ∈ P ⁿ .

Note that µ is possibly a nite support measure, e.g., a quadrature rule itself. The proof relies on the Caratheodory Th. in convex geometry.

Approx. Tchakaloff Points

We can nd approximate solution to V ^t c − b = 0 (V is the Vandermonde matrix at X and b is the moment vector) up to a moment residual  << 1.

Then for any datum f 

   

M

X

i=1

f (x _i )λ _i −

m

X

i=1

f (x _i )w _i     

≤ C _n ()E _n (f ) + kf k _`

²

λ

. Here

C() := 2(µ(X) + p

µ(X)), E _n (f ) = min

p∈P

ⁿ

kf − pk _`

^∞

_(X) .

Compressed Quadrature

Assume X := {x ¹ , . . . , x _M } , M > N and µ := P ^M _i=1 λ _i δ _x

_i

is positive.

Then by Tchakalo theorem we can nd m < M points of X and m positive weights w ⁱ such that (up to re-ordering the sum)

M

X

i=1

p(x _i )λ _i =

m

X

i=1

p(x _i )w _i , ∀p ∈ P ⁿ .

ˆ Compress-ratio M/m may be large!

ˆ Proof of theorem is not constructive.

Compression of LS

Consider the case X = {x ¹ , . . . , x _M } , M > dim P ²ⁿ and λ = (1, 1, . . . , 1).

Let x ¹ , . . . x _m , w ¹ , . . . , w _m be Tchakalo points and weights of degree 2n extracted from X, then

kpk ² _`

2

=

M

X

i=1

p(x _i ) ² =

m

X

i=1

p(x _i ) ² w _i =: kpk ² _`

2

w

, ∀p ∈ P ⁿ .

Denote by L ⁿ standard LS of degree n and L ^c n w -weighted least squares on -approximated Tchakalo points.

Error estimates:

kf − L _n f k _`

²

_(X) ≤ √

M E _n (f ) kf − L ^c _n f k _`

²

_(X) ≤



1 +

s

1 +  √ M 1 −  √

M





√

M E _n (f ).

Linear Programming

Let V ^i,j = q _j (x _i ) be the Vandermonde matrix at X of a basis {q ¹ , . . . q _N } of P ⁿ . Consider the linear programming problem

( min c ^t u , subject to

V ^t u = b, u ∈ (R ⁺ ) ^M . (LP)

Here c is chosen to be linearly independent from the rows of V ^t , the feasible region is a polytope and the vertex are sparse candidate solutions.

Standard approach → simplex method.

Quadratic Programming

As an alternative, we may seek for a sparse, non-negative solution to the moment problem by minimizing the ` ² norm of the residue

( min kV ^t u − bk ₂ , subject to

u ∈ (R ⁺ ) ^M . (QP)

Such a problem can be solved by the lsqnonneg matlab native function, which implements a variant of the Lawson-Hanson method.

Compression of Polynomial Meshes

Admissible polynomial meshes are sequence {X ⁿ } of nite subsets of a given polynomial determining compact set K ⊂ R ^d satisfying

kpk _K ≤ C _n kpk _X

_n

, ∀p ∈ P ⁿ ,

where C ⁿ = O(n ^α ) and M ⁿ := Card X _n = O(n ^β ). Least squares approxi- mation of f ∈ C(K) has the nearly optimal property

kL _X

_n

k := sup

f ∈C(K)

kL _X

_n

f k _K /kf k _K ≤ C _n p

M _n .

If M ⁿ > dim P ²ⁿ we can use Tchakalo points T ²ⁿ extraction as a thinning of X ⁿ and we get the norm estimate

kL _T

_2n

k := sup

f ∈C(K)

kL _T

_2n

f k _K /kf k _K ≤ C _n p

M _n 

1 −  p

M _n  ^1/2 .

Experiment: Pipe-Mania Domain

−1 −0.5 0 0.5 1

−1

−0.8

−0.6

−0.4

−0.2 0 0.2 0.4 0.6 0.8 1

10⁰ 10¹

10⁰ 10¹ 10² 10³

10⁴ starting card compressed card

error amplification factor

Left: the 14415 blue quadrature points are the support of an algebraic quadrature rule of degree 60. The 1891 black points, extracted by quadratic programming,

ts the moments up to an absolute error of 1.2215 · 10

⁻¹⁴

.

Right: Comparison among the input and output cardinalities and the error am- plication factor passing from standard LS to CATCH-LS.

References

[1] J.P. Calvi and N. Levenberg. Levenberg, uniform approximation by discrete least squares polynomials. JAT, 152, 2008.

[2] R.E. Curto and L.A. Fialkow. A duality proof of Tchakalo theorem. JMAA, 269, 2002.

[3] S. De Marchi, F. Piazzon, A. Sommariva, and M. Vianello. Polynomial meshes: Computation and approximation. Proceedings of CMMSE, 152, 2015.

[4] A. Sommariva and M. Vianello. Compression of multivariate discrete measures and applications. Numer. Funct. Anal. Optim., 36, 2015.

[5] A. Sommariva and M. Vianello. Compressed sampling inequalities by Tchakalo theorem. Math. Ineq.Appl., 19, 2016.