Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Matrix product constraints by projection methods

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

The decomposition of a matrix, as a product of factors with particular properties, is a much used tool in numerical analysis. Here we develop methods for decomposing a matrix C into a product XY, where the factors X and Y are required to minimize their distance from an arbitrary pair \(X_0\) and \(Y_0\). This type of decomposition, a projection to a matrix product constraint, in combination with projections that impose structural properties on X and Y, forms the basis of a general method of decomposing a matrix into factors with specified properties. Results are presented for the application of these methods to a number of hard problems in exact factorization.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

Notes

  1. This is equivalent to the behavior of the probability that M random points on the \((N-1)\)-sphere all lie within the same hemisphere, an old problem apparently first analyzed by Ludwig Schläfli.

References

  1. Elser, V.: Solution of the crystallographic phase problem by iterated projections. Acta Cryst. Sect. A 59, 201–209 (2003)

    Article  Google Scholar 

  2. Tadej, W., Zyczkowski, K.: A concise guide to complex Hadamard matrices. Open Syst. Inf. Dyn. 13, 133–177 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  3. Gillis, N., Glineur, F.: On the geometric interpretation of the nonnegative rank. Linear Algebra Appl. 437, 2685–2712 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  4. Gravel, S., Elser, V.: Divide and concur: a general approach to constraint satisfaction. Phys. Rev. E 78, 036706 (2008)

    Article  Google Scholar 

  5. Conway, J.H., Sloane, N.J.A.: Fast quantizing and decoding algorithms for lattice quantizers and codes. IEEE Trans. Inf. Theory 28, 227–232 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  6. Boyd, S., et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2011)

    Article  Google Scholar 

  7. Bauschke, H.H., Combettes, P.L., Luke, D.R.: Finding best approximation pairs relative to two closed convex sets in Hilbert spaces. J. Approx. Theory 79, 418–443 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  8. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Recent results on Douglas-Rachford methods for combinatorial optimization problems. J. Optim. Theory Appl. 163, 1–30 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  9. Aragón Artacho, F.J., Borwein, J.M., Tam, M.K.: Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem. J. Glob. Optim. 65, 309 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  10. Elser, V.: The complexity of bit retrieval. arXiv:1601.03428 (2016) (submitted)

  11. Orrick, W.P.: The maximal -1,1-determinant of order 15. Metrika 62, 195–219 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bomze, I.M., Schachinger, W., Ullrich, R.: New lower bounds and asymptotics for the cp-rank. SIAM. J. Matrix Anal. Appl. 36, 20–37 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  13. Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann. 261, 515534 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gentry, C., Szydlo, M.: Cryptanalysis of the Revised NTRU Signature Scheme, Advances in Cryptology, EUROCRYPT. Lecture Notes in Computer Science, Vol. 2002. Springer, 299–320 (2002)

  15. Vandaele, A., Gillis, N., Glineur, F., Tuyttens, D.: Heuristics for exact nonnegative matrix factorization. J. Glob. Optim. 65, 369 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  16. Vavasis, S.: On the complexity of nonnegative matrix factorization. SIAM J. Optimiz. 20, 1364–1377 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Hogg, T., Huberman, B. A., Williams, C. (eds.) Artificial Intelligence. Special Issue on Frontiers in Problem Solving: Phase Transitions and Complexity, vol. 81, pp. 1-347 (1996)

  18. Hrubeš, P.: On the nonnegative rank of distance matrices. Inform. Process. Lett. 112, 457–461 (2012)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

I thank Nicolas Gillis and Arnaud Vandaele for providing difficult instances of non-negative factorization.

Author information

Authors and Affiliations

  1. Department of Physics, Cornell University, Ithaca, NY, USA

    Veit Elser

Authors
  1. Veit Elser
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Veit Elser.

Additional information

Dedicated to the memory of Jonathan Borwein

Most of this work was competed on sabbatical at Disney Research, Boston. I thank Disney and the Simons Foundation for financial support during that period.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Elser, V. Matrix product constraints by projection methods. J Glob Optim 68, 329–355 (2017). https://doi.org/10.1007/s10898-016-0466-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-016-0466-9

Keywords

Search

Navigation