Chia-Tche Chang

---

‣ Abstract: We describe several approximation algorithms for the joint spectral radius and compare their performance on a large number of test cases. The joint spectral radius of a set M of n x n matrices is the maximal asymptotic growth rate that can be obtained by forming products of matrices from M. This quantity is NP-hard to compute and appears in many areas, including in system theory, combinatorics and information theory. A dozen algorithms have been proposed this last decade for approximating the joint spectral radius but little is known about their practical efficiency. We overview these approximation algorithms and classify them in three categories: approximation obtained by examining long products, by building a specific matrix norm, and by using optimization-based techniques. All these algorithms are now implemented in a (freely available) Matlab toolbox that was released in 2011. This toolbox allows us to present a comparison of the approximations obtained on a large number of test cases as well as on sets of matrices taken from the literature. Finally, in our comparison we include a method, available in the toolbox, that combines different existing algorithms and that is the toolbox's default method. This default method was able to find optimal products for all test cases of dimension less than four.

‣ Full reference: C.-T. Chang and V.D. Blondel. An experimental study of approximation algorithms for the joint spectral radius. Numerical Algorithms, VV(N), MMM, 2012.

‣ Resources: Preprint The JSR Toolbox BibTeX

---

‣ Abstract: An exact algorithm to compute the optimal 3D oriented bounding box has been published in 1985 by Joseph O'Rourke, but it is slow and extremely hard to implement. In this talk we propose a new approach, where the computation of the minimal-volume OBB is formulated as an unconstrained optimization problem on the rotation group SO(3). It is solved using a hybrid method combining the genetic and Nelder-Mead algorithms. This method is analyzed and then compared to the current state-of-the-art techniques. It is shown to be either faster or more reliable for any accuracy.

‣ Full reference: C.-T. Chang, B. Gorissen and S. Melchior. Fast oriented bounding box optimization on the rotation group SO(3, R). ACM Transactions on Graphics, 30(5), Oct., 2011.

‣ Resources: Preprint Matlab Code ACM Digital Library BibTeX

---

‣ Abstract: Algorithms computing minimal-volume OBBs are usually approximations or heuristics that may be far from optimal. The only exact algorithm (by O'Rourke) is slow and hard to implement. We propose a hybrid method combining genetic and Nelder-Mead algorithms that appears to be faster or more reliable for any accuracy.

‣ Full reference: C.-T. Chang, B. Gorissen and S. Melchior. Fast oriented bounding box optimization on the rotation group SO(3, R). ACM SIGGRAPH Asia 2012, Singapore, Nov. 2012. TOG paper.

‣ Resources: Slides ACM Digital Library

---

‣ Abstract: The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate of products of matrices in the set. This quantity appears in many applications but is known to be difficult to approximate. Several approaches to approximate the joint spectral radius involve the construction of long products of matrices, or the construction of an appropriate extremal matrix norm. In this article we present a brief overview of several recent approximation algorithms and introduce a genetic algorithm approximation method. This new method does not give any accuracy guarantees but is quite fast in comparison to other techniques. The performances of the different methods are compared and are illustrated on some benchmark examples. Our results show that, for large sets of matrices or matrices of large dimension, our genetic algorithm may provide better estimates or estimates for situations where these are simply too expensive to compute with other methods. As an illustration of this we compute in less than a minute a bound on the capacity of a code avoiding a given forbidden pattern that improves the bound currently reported in the literature.

‣ Full reference: C.-T. Chang and V.D. Blondel. Approximating the joint spectral radius using a genetic algorithm framework. Proceedings of the 18th IFAC World Congress, Milano, Italy, Aug. 2011.

‣ Resources: Preprint BibTeX

---

‣ Full reference: C.-T. Chang and V.D. Blondel. A genetic algorithm approach for the approximation of the joint spectral radius. Proceedings of the 30th Benelux Meeting on Systems and Control (BMSC11), Lommel, Belgium, Mar. 2011.

‣ Resources: Abstract Slides BibTeX

---

‣ Abstract: The joint spectral radius of a set of matrices is a measure of the maximal asymptotic growth rate of products of matrices in the set. This quantity appears in many applications but is known to be difficult to approximate. Several approaches to compute the joint spectral radius involve the construction of large sets of long products of matrices, or the construction of an appropriate extremal matrix norm. In this article we present a brief overview of several recent algorithms and methods that use the extremal norm approach. The performances of the methods are compared and are illustrated on a simple numerical example.

‣ Full reference: C.-T. Chang and V.D. Blondel. A comparison of extremal norms methods to approximate the joint spectral radius. 2010. Submitted to 49th IEEE Conference on Decision and Control (CDC10).

---

‣ Full reference: C.-T. Chang and V.D. Blondel. A comparison of approximation algorithms for the joint spectral radius. Proceedings of the 29th Benelux Meeting on Systems and Control (BMSC10), Heeze, The Netherlands, Mar. 2010.

‣ Resources: Abstract BibTeX

---

‣ Full reference: C.-T. Chang, R.M. Jungers and V.D. Blondel. On the growth rate of matrices with row uncertainties. Proceedings of the 14th Belgian-French-German Conference on Optimization (BFG09), Leuven, Belgium, Sept. 2009.

‣ Resources: Abstract BibTeX

---

‣ Abstract: Optimization is a major field in applied mathematics. Many applications involve the search of the best solution to a problem according to some criterion. Depending on the considered optimization problem, finding the best solution is not always possible in a reasonable amount of time. Heuristic algorithms are often used when the problem is too difficult to solve exactly. These methods are used to speed up the search for a good solution but they do not guarantee that an optimal solution will be found. In this thesis, we explore such heuristic approaches for three different matrix problems. First, we study the minimum-volume bounding box problem, which consists in finding the smallest rectangular parallelepiped enclosing a given set of points in the three-dimensional space. This problem appears for example in collision detection, which is a very important issue in computational geometry and computer graphics. In these applications, a solution has to be determined in a very short amount of time. We propose a new hybrid algorithm able to approximate optimal bounding boxes at a low computational cost. In particular, it is several orders of magnitude faster than the only currently known exact algorithm. Second, we investigate the subset selection problem. Given a large set of features, we want to choose a small subset containing the most relevant features while removing the redundant ones. This problem has applications in data mining since this can be seen as a dimensionality reduction problem. We develop several windowed algorithms that tackle the subset selection problem for the maximum-volume criterion, which is NP-hard. Finally, we address the topic of the approximation of the joint spectral radius. This quantity characterizes the growth rate of product of matrices and is NP-hard to approximate. The joint spectral radius appears in many fields, including system theory, graph theory, combinatorics, language theory... We present an experimental study of existing approaches and propose a new genetic-based algorithm that is able to find bounds on the joint spectral radius in a short amount of time.

‣ Full reference: C.-T. Chang. Heuristic optimization methods for three matrix problems. Ph.D. thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2012.

‣ Resources: Thesis Announcement BibTeX

---

‣ Abstract: In this work, we study the capacity of codes that avoid forbidden difference patterns. Given a n-ary alphabet A, we can define another alphabet \tilde{A} whose symbols correspond to differences of elements of A. Given a set D of forbidden words on \tilde{A}, we are interested in the maximal number of strings on A of length n, whose pairwise differences do not contain elements of D. This maximal number grows exponentially with n, and the capacity is defined by the corresponding exponent. It can be computed as the joint spectral radius of a set of matrices, and we study and implement several methods to approximate this capacity.

‣ Full reference: C.-T. Chang. Étude de la capacité de codes évitant des motifs de différence. Master's thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2008. In French.

‣ Resources: BibTeX

---

‣ Abstract: In this work, we study polynomial optimization using the sum-of-squares (SOS) approach. Given a multivariate polynomial p(x), it is not easy to compute the global minimum of p(x) in the general case, but the SOS formulation can provide very good approximations. In particular, the SOS formulation gives the exact solution in several cases, such as univariate polynomials. As the size of the associated semidefinite problem grows exponentially with the degree and the number of variables, the structure of p(x) is analyzed in order to simplify the optimization problem, either using sparsity or symmetry of variables. These algorithms have been implemented and results show that this combination gives efficiently the exact solution in nearly all cases.

‣ Full reference: C.-T. Chang. Polynômes et Sommes de Carrés. Master's thesis, Université catholique de Louvain, Louvain-la-Neuve, Belgium, 2007. In French.

‣ Resources: BibTeX

---

‣ Abstract: Photorealistic realtime rendering and physically correct simulations of 3D scenes are at the bleeding edge of what can be done with today's computers. Such applications involve collision detection and visibility tests using methods based on oriented bounding boxes (OBB) enclosing 3D objects. Joseph O'Rourke published in 1985 an algorithm that computes the exact solution in cubic time, but is extremely hard to implement. In practice, faster PCA-based and brute force heuristics are used. The computation of the minimal-volume OBB is formulated as an unconstrained optimization problem on the rotation group SO(3). It is solved using a hybrid method combining the genetic and Nelder-Mead algorithms. This method is analyzed then compared to the current state-of-the-art, and it turns out to be either faster or more accurate.

‣ Full reference: C.-T. Chang and B. Gorissen. Fast computation on SO(3) of optimal oriented bounding box. CESAME Seminar, Université catholique de Louvain, Louvain-la-Neuve, Belgium, Oct. 2009.

‣ Resources: Slides