Invariant polytopes of sets of matrices with application to regularity of wavelets and subdivisions. (English) Zbl 1382.15033
Summary: We generalize the recent invariant polytope algorithm for computing the joint spectral radius and extend it to a wider class of matrix sets. This, in particular, makes the algorithm applicable to sets of matrices that have finitely many spectrum maximizing products. A criterion of convergence of the algorithm is proved. As an application we solve two challenging computational open problems. First we find the regularity of the Butterfly subdivision scheme for various parameters \(\omega\). In the “most regular” case \(\omega = \frac{1}{16}\), we prove that the limit function has Hölder exponent 2 and its derivative is “almost Lipschitz” with logarithmic factor 2. Second we compute the Hölder exponent of Daubechies wavelets of high order.
MSC:
| 15A60 | Norms of matrices, numerical range, applications of functional analysis to matrix theory |
| 15A18 | Eigenvalues, singular values, and eigenvectors |
| 42C40 | Nontrigonometric harmonic analysis involving wavelets and other special systems |
| 90C90 | Applications of mathematical programming |
Keywords:
joint spectral radius; invariant polytope algorithm; dominant products; balancing; subdivision schemes; butterfly scheme; Daubechies waveletsReferences:
| [1] | N. Alkalai and N. Dyn, {\it Optimising 3D triangulations: Improving the initial triangulation for the Butterfly subdivision scheme}, in Advances in Multiresolution for Geometric Modelling, Math. Vis., Springer, Berlin, 2005, pp. 231-244. · Zbl 1065.65024 |
| [2] | T. Ando and M.-H. Shih, {\it Simultaneous contractibility}, SIAM J. Matrix Anal. Appl., 19 (1998), pp. 487-498. · Zbl 0912.15033 |
| [3] | M. A. Berger and Y. Wang, {\it Bounded semigroups of matrices}, Linear Algebra Appl., 166 (1992) pp. 21-27. · Zbl 0818.15006 |
| [4] | V.D. Blondel and Yu. Nesterov, {\it Computationally efficient approximations of the joint spectral radius}, SIAM J. Matrix Anal., 27 (2005), pp. 256-272. · Zbl 1089.65031 |
| [5] | V.D. Blondel, Y. Nesterov, and J. Theys, {\it On the accuracy of the ellipsoid norm approximation of the joint spectral radius}, Linear Algebra Appl., 394 (2005), pp. 91-107. · Zbl 1086.15020 |
| [6] | V. Blondel and J. Tsitsiklis, {\it Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard}, IEEE Trans. Automat. Control, 45 (2000), pp. 1762-1765. · Zbl 0990.93073 |
| [7] | V. Blondel and J. Tsitsiklis, {\it The boundedness of all products of a pair of matrices is undecidable}, Systems Control Lett., 41 (2000), pp. 135-140. · Zbl 0985.93042 |
| [8] | A. S. Cavaretta, W. Dahmen, and C. A. Micchelli, {\it Stationary subdivision,} Mem. Amer. Math. Soc., 453 (1991) pp. 1-185. · Zbl 0741.41009 |
| [9] | A. Cicone and V. Yu. Protasov, {\it Fast computation of tight bounds for the joint spectral radius}, preprint, http://people.math.gatech.edu/ acicone3 (2013). |
| [10] | A. Cohen and I. Daubechies, {\it A new technique to estimate the regularity of refinable functions}, Rev. Mat. Iberoam., 12 (1996), pp. 527-591. · Zbl 0879.65102 |
| [11] | D. Collela and C. Heil, {\it Characterization of scaling functions: I. Continuous solutions}, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 496-518. · Zbl 0797.39006 |
| [12] | I. Daubechies, {\it Orthonormal bases of compactly supported wavelets}, Comm. Pure Appl. Math., 41 (1988) pp. 909-996. · Zbl 0644.42026 |
| [13] | I. Daubechies and J. Lagarias, {\it Two-scale difference equations. II. Local regularity, infinite products of matrices and fractals}, SIAM J. Math. Anal., 23 (1992), pp. 1031-1079. · Zbl 0788.42013 |
| [14] | G. Deslauriers and S. Dubuc, {\it Symmetric iterative interpolation processes}, Constr. Approx., 5 (1989) pp. 49-68. · Zbl 0659.65004 |
| [15] | S. Dubuc, {\it Interpolation through an iterative scheme}, J. Math. Anal. Appl., 114 (1986), pp. 185-204. · Zbl 0615.65005 |
| [16] | N. Dyn, D. Levin, and G. A. Gregory, {\it A butterfly subdivision scheme for surface interpolation with tension control}, ACM Trans. Graphics, 9 (1990), pp. 160-169. · Zbl 0726.68076 |
| [17] | L. Elsner, {\it The generalized spectral-radius theorem: An analytic-geometric proof}, Linear Algebra Appl., 220 (1995), pp. 151-159. · Zbl 0828.15006 |
| [18] | N. J. Fine and H. S. Wilf, {\it Uniqueness theorems for periodic functions}, Proc. Amer. Math. Soc., 16 (1965), pp. 109-114. · Zbl 0131.30203 |
| [19] | G. Golub and C. Van Loan, {\it Matrix Computations}, Johns Hopkins Stud. Math. Sci., Johns Hopkins University Press, Baltimore, MD, 2013. · Zbl 1268.65037 |
| [20] | G. Gripenberg, {\it Computing the joint spectral radius}, Linear Algebra Appl., 234 (1996), pp. 43-60. · Zbl 0863.65017 |
| [21] | N. Guglielmi and V. Yu. Protasov, {\it Exact computation of joint spectral characteristics of matrices}, Found. Comput. Math., 13 (2013), pp. 37-97. · Zbl 1273.65054 |
| [22] | N. Guglielmi, F. Wirth, and M. Zennaro, {\it Complex polytope extremality results for families of matrices}, SIAM J. Matrix Anal. Appl., 27 (2005), pp. 721-743. · Zbl 1099.15023 |
| [23] | N. Guglielmi, C. Manni, and D. Vitale, {\it Convergence analysis of \(C^2\) Hermite interpolatory subdivision schemes by explicit joint spectral radius formulas}, Linear Algebra Appl., 434 (2011), pp. 784-902. · Zbl 1210.65058 |
| [24] | N. Guglielmi and M. Zennaro. {\it On the asymptotic properties of a family of matrices}, Linear Algebra Appl., 322 (2001), pp. 169-192. · Zbl 0971.15016 |
| [25] | N. Guglielmi and M. Zennaro, {\it Balanced complex polytopes and related vector and matrix norms}, J. Convex Anal., 14 (2007), pp. 729-766. · Zbl 1128.52010 |
| [26] | N. Guglielmi and M. Zennaro, {\it Finding extremal complex polytope norms for families of real matrices}, SIAM J. Matrix Anal. Appl., 31 (2009), pp. 602-620. · Zbl 1197.93129 |
| [27] | N. Guglielmi and M. Zennaro, {\it Stability of linear problems: Joint spectral radius of sets of matrices}, in Current Challenges in Stability Issues for Numerical Differential Equations, Lecture Notes in Math. 2082, Springer, New York, 2014, pp. 265-313. · Zbl 1318.65081 |
| [28] | J. Hechler, B. Möß ner, and U. Reif, {\it \(C^1\) -continuity of the generalized four-point scheme}, Linear Algebra Appl., 430 (2009), pp. 3019-3029. · Zbl 1187.65011 |
| [29] | R.M. Jungers, {\it The Joint Spectral Radius: Theory and Applications,} Lecture Notes in Control and Inform. Sci. 385, Springer-Verlag, Berlin, 2009. |
| [30] | C. Möller and U. Reif, {\it A tree-based approach to joint spectral radius determination}, Linear Algebra Appl., 563 (2014), pp. 154-170. · Zbl 1300.15004 |
| [31] | I.Y. Novikov, V.Yu. Protasov, and M.A. Skopina, {\it Wavelets Theory}, Transl. Math. Monogr. 239, AMS, Providence, RI, 2011. · Zbl 1213.42002 |
| [32] | P. Oswald, {\it private communication}, 2012. |
| [33] | P.A. Parrilo and A.Jadbabaie, {\it Approximation of the joint spectral radius using sum of squares}, Linear Algebra Appl., 428 (2008), pp. 2385-2402. · Zbl 1151.65032 |
| [34] | V.Yu. Protasov, {\it The joint spectral radius and invariant sets of linear operators}, Fundam. Prikl. Mat., 2 (1996), 205-231. · Zbl 0899.47002 |
| [35] | V.Yu. Protasov, {\it The generalized spectral radius. A geometric approach}, Izv. Math., 61 (1997), pp. 995-1030. · Zbl 0893.15002 |
| [36] | V.Yu. Protasov, {\it Fractal curves and wavelets}, Izv. Math., 70 (2006), pp. 123-162. · Zbl 1157.26003 |
| [37] | V.Yu. Protasov, R.M. Jungers, and V.D. Blondel, {\it Joint spectral characteristics of matrices: A conic programming approach}, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2146-2162. · Zbl 1203.65093 |
| [38] | O. Rioul, {\it Simple regularity criteria for subdivision schemes}, SIAM J. Math. Anal., 23 (1992), pp. 1544-1576. · Zbl 0761.42016 |
| [39] | G.C. Rota and G. Strang, {\it A note on the joint spectral radius}, Kon. Nederl. Acad. Wet. Proc., 63 (1960), pp. 379-381. · Zbl 0095.09701 |
| [40] | P. Shenkman, N. Dyn, and D. Levin, {\it Normals of the butterfly subdivision scheme surfaces and their applications}, J. Comput. Appl. Math., 102 (1999), pp. 157-180. · Zbl 0934.65018 |
| [41] | G. W. Stewart and J. G. Sun, {\it Matrix Perturbation Theory}, Academic Press, New York, 1990. · Zbl 0706.65013 |
| [42] | L. Villemoes {\it Wavelet analysis of refinement equations}, SIAM J. Math. Anal., 25 (1994), pp. 1433-1460. · Zbl 0809.42016 |
| [43] | H. Zhang, Y. Y. Ma, C. Zhang, and S.-W. Jiang, {\it Improved butterfly subdivision scheme for meshes with arbitrary topology}, J. Beijing Inst. Technol., 14 (2005), pp. 217-220. · Zbl 1112.65308 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
