December  2018, 8(4): 413-440. doi: 10.3934/naco.2018026

Optimization problems with orthogonal matrix constraints

1. 

Department of Mathematics and Statistics, Wright State University, 3640 Colonel Glenn Highway Dayton, OH 45435, U.S.A

2. 

Department of Mathematics and Statistics, Air Force Institute of Technology, 2950 Hobson Way, Wright Patterson Air Force Base, OH 45433, USA

* Corresponding author: Manil T. Mohan

M. T. Mohan's current address Department of Mathematics, Indian Institute of Technology Roorkee-IIT Roorkee, Haridwar Highway, Roorkee, Uttarakhand 247 667, INDIA

Received  May 2017 Revised  August 2018 Published  September 2018

The optimization problems involving orthogonal matrices have been formulated in this work. A lower bound for the number of stationary points of such optimization problems is found and its connection to the number of possible partitions of natural numbers is also established. We obtained local and global optima of such problems for different orders and showed their connection with the Hadamard, conference and weighing matrices. The application of general theory to some concrete examples including maximization of Shannon, Rény, Tsallis and Sharma-Mittal entropies for orthogonal matrices, minimum distance orthostochastic matrices to uniform van der Waerden matrices, Cressie-Read and K-divergence functions for orthogonal matrices, etc are also discussed. Global optima for all orders has been found for the optimization problems involving unitary matrix constraints.

Citation: K. T. Arasu, Manil T. Mohan. Optimization problems with orthogonal matrix constraints. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 413-440. doi: 10.3934/naco.2018026
References:
[1] P.-A. AbsilR. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008.  doi: 10.1515/9781400830244.
[2]

K. T. Arasu, M. T. Mohan, A. Pathak and R. J. Ramya, Entropy optimal orthogonal matrices, Submitted for Journal Publication, 2018.

[3]

K. T. Arasu and M. T. Mohan, Entropy of orthogonal matrices and minimum distance orthostochastic matrices from the uniform van der Waerden matrix, Submitted for Journal Publication, 2018.

[4]

R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Springer, New York, 1997 doi: 10.1007/978-1-4612-0653-8.

[5]

O. Chterental and D. Ž. Ɖoković, On orthostochastic, unistochastic and qustochastic matrices, Linear Algebra and its Applications, 428 (2008), 1178-1201.  doi: 10.1016/j.laa.2007.09.022.

[6]

N. Cressie and T. R. C. Read, Multinomial goodness of fit, Journal of the Royal Statistical Society, B, 46 (1984), 440-464. 

[7]

P. DelsarteJ. M. Goethals and J. J. Seidel, Orthogonal matrices with zero diagonal Ⅱ, Canadian Journal of Mathematics, ⅩⅩⅩⅢ (1971), 816-832.  doi: 10.4153/CJM-1971-091-x.

[8]

A. EdelmanT. A. Arias and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM Journal of Matrix Analysis and Applications, 20 (1999), 303-353.  doi: 10.1137/S0895479895290954.

[9]

H. G. GadiyarK. M. Sangeeta MainiR. Padma and H. S. Sharatchandra, Entropy and Hadamard matrices, Journal of Physics A: Mathematical and General, 36 (2003), 109-112.  doi: 10.1088/0305-4470/36/7/103.

[10]

J. Gallier, Basics of Classical Lie Groups: The Exponential Map, Lie Groups, and Lie Algebras, Chapter 14, in "Geometric Methods and Applications", the series Texts in Applied Mathematicsolume, 38 (2001), 367–414. doi: 10.1007/978-1-4613-0137-0_14.

[11]

A. V. GeramitaJ. M. Geramita and J. Seberry, Orthogonal designs, Linear and Multilinear Algebra, 3 (1976), 381-206.  doi: 10.1080/03081087608817121.

[12]

A. V. Geramita and J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York-Basel, 1979.

[13]

B. K. P. Horn, Closed form solution of absolute orientation using unit quaternions, Journal of the Optical Society A, 4 (1987), 629-642.  doi: 10.1364/JOSAA.4.000629.

[14]

Z. Q. Ma, Group Theory for Physicists, World Scientific, Singapore 2007. doi: 10.1142/6596.

[15]

A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer Series in Statistics, New York, 2011. doi: 10.1007/978-0-387-68276-1.

[16]

M. T. Mohan, On some p−almost Hadamard matrices, Accepted in Operators and Matrices, 2018.

[17]

H. Nakzato, Set of 3 × 3 orthostochastic matrices, Nihonkai Mathematics Journal, 7 (1996), 83-100. 

[18]

A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Mathematical Programming, 109 (2007), 283-317.  doi: 10.1007/s10107-006-0033-0.

[19]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. Springer, New York, 2006

[20]

R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.

[21]

D. R. Stinson Combinatorial Designs: Constructions and Analysis, Springer-Verlag New York, Inc., 2004.

[22]

B. D. Sharma and D. P. Mittal, New non-additive measures of entropy for discrete probability distributions, Journal of Mathematical Sciences, 10 (1975), 28-40. 

[23]

F. Szöllősi, Construction, classification and parametrization of complex Hadamard matrices, PhD Thesis, https://arXiv.org/abs/1110.5590, 2011.

[24]

V. WeberJ. Vande VondeleJ. Hütter and A. M. Niklasson, Direct energy functional minimization under orthogonality constraints, The Journal of Chemical Physics, 128 (2008), 84-113.  doi: 10.1063/1.2841077.

[25]

Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., Ser. A, 142 (2013), 397-434.  doi: 10.1007/s10107-012-0584-1.

[26]

K. ŻyczkowskiM. KuśW. Słomczyński and H.-J. Sommers, Random unistochastic matrices, Journal of Physics A: Mathematical and General, 36 (2003), 3425-3450.  doi: 10.1088/0305-4470/36/12/333.

show all references

References:
[1] P.-A. AbsilR. Mahony and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2008.  doi: 10.1515/9781400830244.
[2]

K. T. Arasu, M. T. Mohan, A. Pathak and R. J. Ramya, Entropy optimal orthogonal matrices, Submitted for Journal Publication, 2018.

[3]

K. T. Arasu and M. T. Mohan, Entropy of orthogonal matrices and minimum distance orthostochastic matrices from the uniform van der Waerden matrix, Submitted for Journal Publication, 2018.

[4]

R. Bhatia, Matrix Analysis, Graduate Texts in Mathematics, Springer, New York, 1997 doi: 10.1007/978-1-4612-0653-8.

[5]

O. Chterental and D. Ž. Ɖoković, On orthostochastic, unistochastic and qustochastic matrices, Linear Algebra and its Applications, 428 (2008), 1178-1201.  doi: 10.1016/j.laa.2007.09.022.

[6]

N. Cressie and T. R. C. Read, Multinomial goodness of fit, Journal of the Royal Statistical Society, B, 46 (1984), 440-464. 

[7]

P. DelsarteJ. M. Goethals and J. J. Seidel, Orthogonal matrices with zero diagonal Ⅱ, Canadian Journal of Mathematics, ⅩⅩⅩⅢ (1971), 816-832.  doi: 10.4153/CJM-1971-091-x.

[8]

A. EdelmanT. A. Arias and S. T. Smith, The geometry of algorithms with orthogonality constraints, SIAM Journal of Matrix Analysis and Applications, 20 (1999), 303-353.  doi: 10.1137/S0895479895290954.

[9]

H. G. GadiyarK. M. Sangeeta MainiR. Padma and H. S. Sharatchandra, Entropy and Hadamard matrices, Journal of Physics A: Mathematical and General, 36 (2003), 109-112.  doi: 10.1088/0305-4470/36/7/103.

[10]

J. Gallier, Basics of Classical Lie Groups: The Exponential Map, Lie Groups, and Lie Algebras, Chapter 14, in "Geometric Methods and Applications", the series Texts in Applied Mathematicsolume, 38 (2001), 367–414. doi: 10.1007/978-1-4613-0137-0_14.

[11]

A. V. GeramitaJ. M. Geramita and J. Seberry, Orthogonal designs, Linear and Multilinear Algebra, 3 (1976), 381-206.  doi: 10.1080/03081087608817121.

[12]

A. V. Geramita and J. Seberry, Orthogonal Designs: Quadratic Forms and Hadamard Matrices, Marcel Dekker, New York-Basel, 1979.

[13]

B. K. P. Horn, Closed form solution of absolute orientation using unit quaternions, Journal of the Optical Society A, 4 (1987), 629-642.  doi: 10.1364/JOSAA.4.000629.

[14]

Z. Q. Ma, Group Theory for Physicists, World Scientific, Singapore 2007. doi: 10.1142/6596.

[15]

A. W. Marshall, I. Olkin and B. C. Arnold, Inequalities: Theory of Majorization and Its Applications, Springer Series in Statistics, New York, 2011. doi: 10.1007/978-0-387-68276-1.

[16]

M. T. Mohan, On some p−almost Hadamard matrices, Accepted in Operators and Matrices, 2018.

[17]

H. Nakzato, Set of 3 × 3 orthostochastic matrices, Nihonkai Mathematics Journal, 7 (1996), 83-100. 

[18]

A. Nemirovski, Sums of random symmetric matrices and quadratic optimization under orthogonality constraints, Mathematical Programming, 109 (2007), 283-317.  doi: 10.1007/s10107-006-0033-0.

[19]

J. Nocedal and S. J. Wright, Numerical Optimization, Springer Series in Operations Research and Financial Engineering, 2nd ed. Springer, New York, 2006

[20]

R. E. A. C. Paley, On orthogonal matrices, Journal of Mathematics and Physics, 12 (1933), 311-320.  doi: 10.1002/sapm1933121311.

[21]

D. R. Stinson Combinatorial Designs: Constructions and Analysis, Springer-Verlag New York, Inc., 2004.

[22]

B. D. Sharma and D. P. Mittal, New non-additive measures of entropy for discrete probability distributions, Journal of Mathematical Sciences, 10 (1975), 28-40. 

[23]

F. Szöllősi, Construction, classification and parametrization of complex Hadamard matrices, PhD Thesis, https://arXiv.org/abs/1110.5590, 2011.

[24]

V. WeberJ. Vande VondeleJ. Hütter and A. M. Niklasson, Direct energy functional minimization under orthogonality constraints, The Journal of Chemical Physics, 128 (2008), 84-113.  doi: 10.1063/1.2841077.

[25]

Z. Wen and W. Yin, A feasible method for optimization with orthogonality constraints, Math. Program., Ser. A, 142 (2013), 397-434.  doi: 10.1007/s10107-012-0584-1.

[26]

K. ŻyczkowskiM. KuśW. Słomczyński and H.-J. Sommers, Random unistochastic matrices, Journal of Physics A: Mathematical and General, 36 (2003), 3425-3450.  doi: 10.1088/0305-4470/36/12/333.

Figure 1.  n versus d graph
Figure 2.  Rényi entropy of $2\times 2$ orthogonal matrices
Figure 3.  Sharma-Mittal entropy of $2\times 2$ orthogonal matrices
Figure 4.  Tsallis entropy of $2\times 2$ orthogonal matrices
Table 1.  1 $\leq n\leq $ 20.
$n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$ $n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$
$1$ ${\rm H}_1$ $0$ $11$ $\frac{1}{3}{\rm C}_{10}\oplus{\rm H}_1^*$ $1.054$
$2$ $\frac{1}{\sqrt{2}}{\rm H}_2$ $0$ $12$ $\frac{1}{2\sqrt{3}}{\rm H}_{12}$ $0$
$3$ ${\rm K}_3$ $0.471$ $13$ $\frac{1}{3}{\rm W}_{13, 9}$ $0.667$
$4$ $\frac{1}{2}{\rm H}_4$ $0$ $14$ $\frac{1}{\sqrt{13}}{\rm C}_{14}$ $0.277$
$5$ ${\rm K}_5$ $0.400$ $15$ ${\rm K}_3\otimes{\rm K}_5^{\dagger}$ $0.646$
$6$ $\frac{1}{\sqrt{5}}{\rm C}_6$ $0.447$ $16$ $\frac{1}{4}{\rm H}_{16}$ $0$
$7$ $\frac{1}{2}{\rm W}_{7, 4}$ $0.866$ $17$ $\frac{1}{3}{\rm W}_{17, 9}$ $0.943$
$8$ $\frac{1}{2\sqrt{2}}{\rm H}(8)$ $0$ $18$ $\frac{1}{\sqrt{17}}{\rm C}_{18}$ $0.243$
$9$ ${\rm K}_3\otimes{\rm K}_3$ $0.703$ $19$ $\frac{1}{\sqrt{17}}{\rm C}_{18}\oplus{\rm H}_1^*$ $1.029$
$10$ $\frac{1}{3}{\rm C}_{10}$ $0.333$ $20$ $\frac{1}{2\sqrt{5}}{\rm H}_{20}$ $0$
$^*$By Proposition 4.2, these orthogonal matrices are saddle points and not local minima. The weighing matrices ${\rm W}_{11, 4}$ and ${\rm W}_{19, 9}$ exists for orders $11$ and $19$, but they are also saddle points. The orthostochastic matrices corresponding to the orthogonal matrices $\frac{1}{2}{\rm W}_{11, 4}$ and $\frac{1}{3}{\rm W}_{19, 9}$ are at distances $1.323>1.054$ and $1.054>1.029$, respectively from the the uniform van der Waerden matrices ${\rm J}_{11}$ and ${\rm J}_{19}$. $^{\dagger}$For order $15$, weighing matrix ${\rm W}_{15, 9}$ exist, which are also local minima, by Proposition 4.11. But the orthostochastic matrix corresponding to the orthogonal matrix $\frac{1}{3}{\rm W}_{15, 9}$ is at a distance $0.817>0.646$, from the uniform van der Waerden matrix ${\rm J}_{15}$.
$n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$ $n$ Orthogonal matrix $d({\rm J}_n, {\rm B}_n)$
$1$ ${\rm H}_1$ $0$ $11$ $\frac{1}{3}{\rm C}_{10}\oplus{\rm H}_1^*$ $1.054$
$2$ $\frac{1}{\sqrt{2}}{\rm H}_2$ $0$ $12$ $\frac{1}{2\sqrt{3}}{\rm H}_{12}$ $0$
$3$ ${\rm K}_3$ $0.471$ $13$ $\frac{1}{3}{\rm W}_{13, 9}$ $0.667$
$4$ $\frac{1}{2}{\rm H}_4$ $0$ $14$ $\frac{1}{\sqrt{13}}{\rm C}_{14}$ $0.277$
$5$ ${\rm K}_5$ $0.400$ $15$ ${\rm K}_3\otimes{\rm K}_5^{\dagger}$ $0.646$
$6$ $\frac{1}{\sqrt{5}}{\rm C}_6$ $0.447$ $16$ $\frac{1}{4}{\rm H}_{16}$ $0$
$7$ $\frac{1}{2}{\rm W}_{7, 4}$ $0.866$ $17$ $\frac{1}{3}{\rm W}_{17, 9}$ $0.943$
$8$ $\frac{1}{2\sqrt{2}}{\rm H}(8)$ $0$ $18$ $\frac{1}{\sqrt{17}}{\rm C}_{18}$ $0.243$
$9$ ${\rm K}_3\otimes{\rm K}_3$ $0.703$ $19$ $\frac{1}{\sqrt{17}}{\rm C}_{18}\oplus{\rm H}_1^*$ $1.029$
$10$ $\frac{1}{3}{\rm C}_{10}$ $0.333$ $20$ $\frac{1}{2\sqrt{5}}{\rm H}_{20}$ $0$
$^*$By Proposition 4.2, these orthogonal matrices are saddle points and not local minima. The weighing matrices ${\rm W}_{11, 4}$ and ${\rm W}_{19, 9}$ exists for orders $11$ and $19$, but they are also saddle points. The orthostochastic matrices corresponding to the orthogonal matrices $\frac{1}{2}{\rm W}_{11, 4}$ and $\frac{1}{3}{\rm W}_{19, 9}$ are at distances $1.323>1.054$ and $1.054>1.029$, respectively from the the uniform van der Waerden matrices ${\rm J}_{11}$ and ${\rm J}_{19}$. $^{\dagger}$For order $15$, weighing matrix ${\rm W}_{15, 9}$ exist, which are also local minima, by Proposition 4.11. But the orthostochastic matrix corresponding to the orthogonal matrix $\frac{1}{3}{\rm W}_{15, 9}$ is at a distance $0.817>0.646$, from the uniform van der Waerden matrix ${\rm J}_{15}$.
[1]

Ke Wei, Jian-Feng Cai, Tony F. Chan, Shingyu Leung. Guarantees of riemannian optimization for low rank matrix completion. Inverse Problems and Imaging, 2020, 14 (2) : 233-265. doi: 10.3934/ipi.2020011

[2]

Meijuan Shang, Yanan Liu, Lingchen Kong, Xianchao Xiu, Ying Yang. Nonconvex mixed matrix minimization. Mathematical Foundations of Computing, 2019, 2 (2) : 107-126. doi: 10.3934/mfc.2019009

[3]

Paul Skerritt, Cornelia Vizman. Dual pairs for matrix groups. Journal of Geometric Mechanics, 2019, 11 (2) : 255-275. doi: 10.3934/jgm.2019014

[4]

Adel Alahmadi, Hamed Alsulami, S.K. Jain, Efim Zelmanov. On matrix wreath products of algebras. Electronic Research Announcements, 2017, 24: 78-86. doi: 10.3934/era.2017.24.009

[5]

Francis C. Motta, Patrick D. Shipman. Informing the structure of complex Hadamard matrix spaces using a flow. Discrete and Continuous Dynamical Systems - S, 2019, 12 (8) : 2349-2364. doi: 10.3934/dcdss.2019147

[6]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015

[7]

Shengxin Zhu, Tongxiang Gu, Xingping Liu. AIMS: Average information matrix splitting. Mathematical Foundations of Computing, 2020, 3 (4) : 301-308. doi: 10.3934/mfc.2020012

[8]

Peizhao Yu, Guoshan Zhang, Yi Zhang. Decoupling of cubic polynomial matrix systems. Numerical Algebra, Control and Optimization, 2021, 11 (1) : 13-26. doi: 10.3934/naco.2020012

[9]

Henry Adams, Lara Kassab, Deanna Needell. An adaptation for iterative structured matrix completion. Foundations of Data Science, 2021, 3 (4) : 769-791. doi: 10.3934/fods.2021028

[10]

Jairo Bochi, Michal Rams. The entropy of Lyapunov-optimizing measures of some matrix cocycles. Journal of Modern Dynamics, 2016, 10: 255-286. doi: 10.3934/jmd.2016.10.255

[11]

Yongge Tian. A survey on rank and inertia optimization problems of the matrix-valued function $A + BXB^{*}$. Numerical Algebra, Control and Optimization, 2015, 5 (3) : 289-326. doi: 10.3934/naco.2015.5.289

[12]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883

[13]

Lei Zhang, Anfu Zhu, Aiguo Wu, Lingling Lv. Parametric solutions to the regulator-conjugate matrix equations. Journal of Industrial and Management Optimization, 2017, 13 (2) : 623-631. doi: 10.3934/jimo.2016036

[14]

Heide Gluesing-Luerssen, Fai-Lung Tsang. A matrix ring description for cyclic convolutional codes. Advances in Mathematics of Communications, 2008, 2 (1) : 55-81. doi: 10.3934/amc.2008.2.55

[15]

Houduo Qi, ZHonghang Xia, Guangming Xing. An application of the nearest correlation matrix on web document classification. Journal of Industrial and Management Optimization, 2007, 3 (4) : 701-713. doi: 10.3934/jimo.2007.3.701

[16]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103

[17]

Li Zhang, Xiaofeng Zhou, Min Chen. The research on the properties of Fourier matrix and bent function. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 571-578. doi: 10.3934/naco.2020052

[18]

Angelo B. Mingarelli. Nonlinear functionals in oscillation theory of matrix differential systems. Communications on Pure and Applied Analysis, 2004, 3 (1) : 75-84. doi: 10.3934/cpaa.2004.3.75

[19]

A. Cibotarica, Jiu Ding, J. Kolibal, Noah H. Rhee. Solutions of the Yang-Baxter matrix equation for an idempotent. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 347-352. doi: 10.3934/naco.2013.3.347

[20]

Haixia Liu, Jian-Feng Cai, Yang Wang. Subspace clustering by (k,k)-sparse matrix factorization. Inverse Problems and Imaging, 2017, 11 (3) : 539-551. doi: 10.3934/ipi.2017025

 Impact Factor: 

Metrics

  • PDF downloads (1566)
  • HTML views (1242)
  • Cited by (2)

Other articles
by authors

[Back to Top]