Sparse multivariate function recovery with a high error rate in the evaluations

ABSTRACT

In [Kaltofen and Yang, Proc. ISSAC 2013] we have generalized algebraic error-correcting decoding to multivariate sparse rational function interpolation from evaluations that can be numerically inaccurate and where several evaluations can have severe errors ("outliers"). Here we present a different algorithm that can interpolate a sparse multivariate rational function from evaluations where the error rate is 1/q for any q > 2, which our ISSAC 2013 algorithm could not handle. When implemented as a numerical algorithm we can, for instance, reconstruct a fraction of trinomials of degree 15 in 50 variables with non-outlier evaluations of relative noise as large as 10^-7 and where as much as 1/4 of the 14717 evaluations are outliers with relative error as small as 0.01 (large outliers are easily located by our method).

For the algorithm with exact arithmetic and exact values at non-erroneous points, we provide a proof that for random evaluations one can avoid quadratic oversampling. Our argument already applies to our original 2007 sparse rational function interpolation algorithm [Kaltofen, Yang and Zhi, Proc. SNC 2007], where we have experimentally observed that for T unknown non-zero coefficients in a sparse candidate ansatz one only needs T +O(1) evaluations rather than the proven O(T²) (cf. Candès and Tao sparse sensing). Here we finally can give the probabilistic analysis for this fact.

References

1. Arnold, A., Giesbrecht, M., and Roche, D. S. Faster sparse interpolation of straight-line programs. In CASC (2013), V. P. Gerdt, W. Koepf, E. W. Mayr, and E. V. Vorozhtsov, Eds., vol. 8136 of LNCS, Springer, pp. 61--74.
2. Ben-Or, M., and Tiwari, P. A deterministic algorithm for sparse multivariate polynomial interpolation. In Proc. Twentieth STOC (New York, N.Y., 1988), ACM Press, pp. 301--309.
3. Blahut, R. E. A universal Reed-Solomon decoder. IBM J. Res. Develop. 18, 2 (Mar. 1984), 943--959.
4. Candès, E. J., and Tao, T. Near-optimal signal recovery from random projections: universal encoding strategies. IEEE Trans. Inform. Theory 52 (2004), 5406--5425.
5. Comer, M. T., Kaltofen, E. L., and Pernet, C. Sparse polynomial interpolation and Berlekamp/Massey algorithms that correct outlier errors in input values. In Proc. ISSAC 2012 (New York, N. Y., July 2012), J. van der Hoeven and M. van Hoeij, Eds., ACM, pp. 138--145.
6. Cuyt, A., and Lee, W. Sparse interpolation of multivariate rational functions. TCS 412 (2011), 1445--1456.
7. de Kleine, J., Monagan, M., and Wittkopf, A. Algorithms for the non-monic case of the sparse modular GCD algorithm. In Proc. ISSAC 2005 (New York, N. Y., 2005), M. Kauers, Ed., ACM Press, pp. 124--131.
8. Garg, S., and Schost, Éric. Interpolation of polynomials given by straight-line programs. TCS 410, 27--29 (2009), 2659--2662.
9. Giesbrecht, M., Labahn, G., and Lee, W. Symbolic-numeric sparse interpolation of multivariate polynomials. JSC 44 (2009), 943--959.
10. Kaltofen, E. Factorization of polynomials given by straight-line programs. In Randomness and Computation, S. Micali, Ed. JAI Press Inc., 1989, pp. 375--412.
11. Kaltofen, E. Fifteen years after DSC and WLSS2 What parallel computations I do today {Invited lecture at PASCO 2010}. In Proc. PASCO 2010 (New York, N. Y., July 2010), M. Moreno Maza and J.-L. Roch, Eds., ACM, pp. 10--17.
12. Kaltofen, E., Lakshman Y. N., and Wiley, J. M. Modular rational sparse multivariate polynomial interpolation. In Proc. 1990 Internat. Symp. Symbolic Algebraic Comput. (ISSAC'90) (1990), S. Watanabe and M. Nagata, Eds., ACM Press, pp. 135--139.
13. Kaltofen, E., and Lee, W. Early termination in sparse interpolation algorithms. JSC 36, 3--4 (2003), 365--400.
14. Kaltofen, E., and Nehring, M. Supersparse black box rational function interpolation. In Proc. 2011 Internat. Symp. Symbolic Algebraic Comput. ISSAC 2011 (New York., N. Y., June 2011), A. Leykin, Ed., ACM, pp. 177--185.
15. Kaltofen, E., and Pernet, C. Cauchy interpolation with errors in the values. Submitted manuscript, 13 pages, Dec. 2013.
16. Kaltofen, E., and Yang, Z. On exact and approximate interpolation of sparse rational functions. In Proc. ISSAC 2007 (New York, N. Y., 2007), C. W. Brown, Ed., ACM Press, pp. 203--210.
17. Kaltofen, E., and Yang, Z. Sparse multivariate function recovery from values with noise and outlier errors. In Proc. ISSAC 2013 (New York, N. Y., 2013), M. Kauers, Ed., ACM, pp. 219--226.
18. Kaltofen, E., Yang, Z., and Zhi, L. On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms. In Proc. SNC 2007 (New York, N. Y., 2007), J. Verschelde and S. M. Watt, Eds., ACM Press, pp. 11--17.
19. Mahoney, M. W. Randomized algorithms for matrices and data. URL: http://arxiv.org/abs/1104.5557, 2011.
20. Olshevsky, V., and Shokrollahi, M. A. A displacement approach to decoding algebraic codes. In Algorithms for Structured Matrices: Theory and Applications. AMS, Providence, RI, 2003, pp. 265--292. Contemp. Math., vol. 323.
21. Prony, R. Essai expérimental et analytique sur les lois de la Dilatabilité de fluides élastiques etc. J. de l'École Polytechnique 1 (Floréal et Prairial III (1795)), 24--76.
22. Saraf, S., and Yekhanin, S. Noisy interpolation of sparse polynomials, and applications. In Proc. 26th Annual IEEE Conf. Comp. Complexity (2011), IEEE Comp. Soc., pp. 86--92.
23. Welch, L. R., and Berlekamp, E. R. Error correction of algebraic block codes. US Patent 4,633,470, 1986. Filed 1983.
24. Zippel, R. Interpolating polynomials from their values. JSC 9, 3 (1990), 375--403.
25. Zippel, R. E. Probabilistic algorithms for sparse polynomials. PhD thesis, MIT, Cambridge, USA, Sept. 1979.

Index Terms

• Computing methodologies

  • Symbolic and algebraic manipulation

    • Symbolic and algebraic algorithms

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Interpolation