Document Open Access Logo

Black Box Absolute Reconstruction for Sums of Powers of Linear Forms

Authors Pascal Koiran, Subhayan Saha

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2022.24.pdf
  • Filesize: 0.69 MB
  • 17 pages

Document Identifiers

Author Details

Pascal Koiran
  • Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON Cedex 07, France
Subhayan Saha
  • Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON Cedex 07, France

Cite AsGet BibTex

Pascal Koiran and Subhayan Saha. Black Box Absolute Reconstruction for Sums of Powers of Linear Forms. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FSTTCS.2022.24

Abstract

We study the decomposition of multivariate polynomials as sums of powers of linear forms. We give a randomized algorithm for the following problem: If a homogeneous polynomial f ∈ K[x_1 , . . . , x_n] (where K ⊆ ℂ) of degree d is given as a blackbox, decide whether it can be written as a linear combination of d-th powers of linearly independent complex linear forms. The main novel features of the algorithm are: - For d = 3, we improve by a factor of n on the running time from the algorithm in [Pascal Koiran and Mateusz Skomra, 2021]. The price to be paid for this improvement is that the algorithm now has two-sided error. - For d > 3, we provide the first randomized blackbox algorithm for this problem that runs in time poly(n,d) (in an algebraic model where only arithmetic operations and equality tests are allowed). Previous algorithms for this problem [Kayal, 2011] as well as most of the existing reconstruction algorithms for other classes appeal to a polynomial factorization subroutine. This requires extraction of complex polynomial roots at unit cost and in standard models such as the unit-cost RAM or the Turing machine this approach does not yield polynomial time algorithms. - For d > 3, when f has rational coefficients (i.e. K = ℚ), the running time of the blackbox algorithm is polynomial in n,d and the maximal bit size of any coefficient of f. This yields the first algorithm for this problem over ℂ with polynomial running time in the bit model of computation. These results are true even when we replace ℂ by ℝ. We view the problem as a tensor decomposition problem and use linear algebraic methods such as checking the simultaneous diagonalisability of the slices of a tensor. The number of such slices is exponential in d. But surprisingly, we show that after a random change of variables, computing just 3 special slices is enough. We also show that our approach can be extended to the computation of the actual decomposition. In forthcoming work we plan to extend these results to overcomplete decompositions, i.e., decompositions in more than n powers of linear forms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Computing methodologies → Algebraic algorithms
  • Computing methodologies → Linear algebra algorithms
Keywords
  • reconstruction algorithms
  • tensor decomposition
  • sums of powers of linear forms
  • simultaneous diagonalisation
  • algebraic algorithm
  • black box

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M. Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15(80):2773-2832, 2014. URL: http://jmlr.org/papers/v15/anandkumar14b.html.
  2. Alessandra Bernardi, Alessandro Gimigliano, and Monica Ida. Computing symmetric rank for symmetric tensors. Journal of Symbolic Computation, 46(1):34-53, 2011. Google Scholar
  3. Vishwas Bhargava, Shubhangi Saraf, and Ilya Volkovich. Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits, pages 809-822. Association for Computing Machinery, New York, NY, USA, 2021. URL: https://doi.org/10.1145/3406325.3451096.
  4. Aditya Bhaskara, Moses Charikar, Ankur Moitra, and Aravindan Vijayaraghavan. Smoothed analysis of tensor decompositions. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 594-603, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591881.
  5. L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation. Springer-Verlag, 1998. Google Scholar
  6. L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bulletin of the American Mathematical Society, 21(1):1-46, July 1989. Google Scholar
  7. Jérôme Brachat, Pierre Comon, Bernard Mourrain, and Elias Tsigaridas. Symmetric tensor decomposition. Linear Algebra and its Applications, 433(11-12):1851-1872, 2010. Google Scholar
  8. Enrico Carlini. Reducing the number of variables of a polynomial. In Algebraic geometry and geometric modeling, Math. Vis., pages 237-247. Springer, Berlin, 2006. URL: https://doi.org/10.1007/978-3-540-33275-6_15.
  9. Guillaume Cheze and André Galligo. Four lectures on polynomial absolute factorization. In Solving polynomial equations, pages 339-392. Springer, 2005. Google Scholar
  10. Guillaume Chèze and Grégoire Lecerf. Lifting and recombination techniques for absolute factorization. Journal of Complexity, 23(3):380-420, 2007. Google Scholar
  11. Shuhong Gao. Factoring multivariate polynomials via partial differential equations. Mathematics of computation, 72(242):801-822, 2003. Google Scholar
  12. Ignacio García-Marco, Pascal Koiran, and Timothée Pecatte. Reconstruction algorithms for sums of affine powers. In Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC), pages 317-324, 2017. URL: https://doi.org/10.1145/3087604.3087605.
  13. Ignacio García-Marco, Pascal Koiran, and Timothée Pecatte. Polynomial equivalence problems for sums of affine powers. In Proc. International Symposium on Symbolic and Algebraic Computation (ISSAC), 2018. Google Scholar
  14. Ankit Garg, Nikhil Gupta, Neeraj Kayal, and Chandan Saha. Determinant equivalence test over finite fields and over ℚ. In Electronic Colloquium on Computational Complexity (ECCC), volume 26, page 42, 2019. Google Scholar
  15. Richard Harshman. Foundations of the PARAFAC procedure: Models and conditions for an "explanatory" multimodal factor analysis. UCLA working papers in phonetics, 1970. Google Scholar
  16. Zohar Karnin and Amir Shpilka. Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In 24th Annual IEEE Conference on Computational Complexity (CCC), pages 274-285, 2009. Google Scholar
  17. Neeraj Kayal. Efficient algorithms for some special cases of the polynomial equivalence problem. In Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, January 2011. URL: https://www.microsoft.com/en-us/research/publication/efficient-algorithms-for-some-special-cases-of-the-polynomial-equivalence-problem/.
  18. Neeraj Kayal, Vineet Nair, Chandan Saha, and Sébastien Tavenas. Reconstruction of full rank algebraic branching programs. ACM Transactions on Computation Theory (TOCT), 11(1):2, 2018. Google Scholar
  19. Neeraj Kayal and Chandan Saha. Reconstruction of non-degenerate homogeneous depth three circuits. In Proc. 51st Annual ACM Symposium on Theory of Computing (STOC), pages 413-424, 2019. Google Scholar
  20. Pascal Koiran and Subhayan Saha. Black box absolute reconstruction for sums of powers of linear forms, 2021. URL: https://doi.org/10.48550/arXiv.2110.05305.
  21. Pascal Koiran and Mateusz Skomra. Derandomization and absolute reconstruction for sums of powers of linear forms. Theoretical Computer Science, 887:63-84, 2021. URL: https://doi.org/10.1016/j.tcs.2021.07.005.
  22. T. Kolda and B. Bader. Tensor decompositions and applications. SIAM Rev., 51:455-500, 2009. Google Scholar
  23. A. Moitra. Algorithmic Aspects of Machine Learning. Cambridge University Press, 2018. Google Scholar
  24. Hani Shaker. Topology and factorization of polynomials. Mathematica Scandinavica, pages 51-59, 2009. Google Scholar
  25. Yaroslav Shitov. How hard is the tensor rank? arXiv preprint, 2016. URL: http://arxiv.org/abs/1611.01559.
  26. Amir Shpilka. Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM Journal on Computing, 38(6):2130-2161, 2009. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact