The matrix joint block diagonalization problem (JBDP) of a given matrix set @math is about finding a nonsingular matrix @math such that all @math are block diagonal. It includes the matrix joint diagonalization problem (JBD) as a special case for which all @math are required diagonal. Generically, such a matrix @math may not exist, but there are practically applications such as multidimensional independent component analysis (MICA) for which it does exist under the ideal situation, i.e., no noise is presented. However, in practice noises do get in and, as a consequence, the matrix set is only approximately block diagonalizable, i.e., one can only make all @math nearly block diagonal at best, where @math is an approximation to @math , obtained usually by computation. This motivates us to develop a perturbation theory for JBDP to address, among others, the question: how accurate this @math is. Previously such a theory for JDP has been discussed, but no effort has been attempted for JBDP yet. In this paper, with the help of a necessary and sufficient condition for solution uniqueness of JBDP recently developed in [Cai and Liu, SIAM J. Matrix Anal. Appl. , 38(1):50--71, 2017], we are able to establish an error bound, perform backward error analysis, and propose a condition number for JBDP. Numerical tests validate the theoretical results.
Though tremendous efforts have gone to solve , their perturbation problems had received little or no attention in the past. In fact, today there are only a handful articles written on the perturbations of only. For , Cardoso @cite_8 presented a first order perturbation bound for a set of commuting matrices, and the result was later generalized by Russo @cite_27 . For general , using gradient flows, Afsari @cite_2 studied sensitivity via cost functions and obtained first order perturbation bounds for the diagonalizer. Shi and Cai @cite_15 investigated a normalized through a constrained optimization problem, and obtained an upper bound on certain distance between an approximate diagonalizer of a perturbed optimization problem and an exact diagonalizer of the unperturbed optimization problem.
@cite_15 @cite_27 @cite_2 @cite_8
1614997894 2019543362 2135503775
Recently, the stability of certain topological phases of matter under weak perturbations was proven. Here, we present a short, alternate proof of the same result. We consider models of topological quantum order for which the unperturbed Hamiltonian H 0 can be written as a sum of local pairwise commuting projectors on a D-dimensional lattice. We consider a perturbed Hamiltonian H = H 0 + V involving a generic perturbation V that can be written as a sum of short-range bounded-norm interactions. We prove that if the strength of V is below a constant threshold value then H has well-defined spectral bands originating from the low-lying eigenvalues of H 0. These bands are separated from the rest of the spectrum and from each other by a constant gap. The width of the band originating from the smallest eigenvalue of H 0 decays faster than any power of the lattice size. We consider the model introduced by Bilu and Linial (2010), who study problems for which the optimal clustering does not change when distances are perturbed. They show that even when a problem is NP-hard, it is sometimes possible to obtain efficient algorithms for instances resilient to certain multiplicative perturbations, e.g. on the order of @math for max-cut clustering. (2010) consider center-based objectives, and Balcan and Liang (2011) analyze the @math -median and min-sum objectives, giving efficient algorithms for instances resilient to certain constant multiplicative perturbations. Here, we are motivated by the question of to what extent these assumptions can be relaxed while allowing for efficient algorithms. We show there is little room to improve these results by giving NP-hardness lower bounds for both the @math -median and min-sum objectives. On the other hand, we show that constant multiplicative resilience parameters can be so strong as to make the clustering problem trivial, leaving only a narrow range of resilience parameters for which clustering is interesting. We also consider a model of additive perturbations and give a correspondence between additive and multiplicative notions of stability. Our results provide a close examination of the consequences of assuming stability in data. This work is a follow-up to our previous work "A numerical approach related to defect-type theories for some weakly random problems in homogenization" (preprint available on this archive). It extends and complements, both theoretically and experimentally, the results presented there. Under consideration is the homogenization of a model of a weakly random heterogeneous material. The material consists of a reference periodic material randomly perturbed by another periodic material, so that its homogenized behavior is close to that of the reference material. We consider laws for the random perturbations more general than in our previous work cited above. We prove the validity of an asymptotic expansion in a certain class of settings. We also extend the formal approach introduced in our former work. Our perturbative approach shares common features with a defect-type theory of solid state physics. The computational efficiency of the approach is demonstrated. The matrix joint diagonalization is a fundamental notion for studying the blind signal processing and the independent component analysis. We reformulate some classical results on the topic in terms of shear matrices. These matrices appear naturally in differential geometry and group theory and the present paper deals with certain perturbations of joint diagonalizers for which the knowledge of shear matrices is crucial.