We consider the following constrained Rayleigh quotient optimization problem (CRQopt):

where $A$ is an $n×n$ real symmetric matrix and $C$ is an $n×m$ real matrix. Usually, $m$ « $n$. The problem is also known as the constrained eigenvalue problem in literature since it becomes an eigenvalue problem if the linear constraint $C$^T$v=b$ is removed. We start by transforming CRQopt into an equivalent optimization problem (LGopt) of minimizing the Lagrangian multiplier of CRQopt, and then into another equivalent problem (QEPmin) of finding the smallest eigenvalue of a quadratic eigenvalue problem. Although these equivalences have been discussed in literature, it appears to be the first time that they are rigorously justified in this paper. In the second part, we present numerical algorithms for solving LGopt and QEPmin based on Krylov subspace projection. The basic idea is to first project LGopt and QEPmin onto Krylov subspaces to yield problems of the same types but of much smaller sizes, and then solve the reduced problems by direct methods, which is either a secular equation solver (in the case of LGopt) or an eigensolver (in the case of QEPmin). We provide convergence analysis for the proposed algorithms and present error bounds. The sharpness of the error bounds is demonstrated by examples, although in applications the algorithms often converge much faster than the bounds suggest. Finally, we apply the new algorithms to semi-supervised learning in the context of constrained clustering.

In structured matrix computations, existing rank structures such as hierarchically semiseparable (HSS) forms admit fast and stable factorizations. However, for discretized problems, such forms are restricted to 1D cases. In this work, we propose a framework to break such a 1D barrier. We study the feasibility of designing multi-layer hierarchically semiseparable (MHS) structures for the approximation of dense matrices arising from multi-dimensional discretized problems such as certain integral operators. The MHS framework extends HSS forms to higher dimensions via the integration of multiple layers of structures, i.e., structures within the dense generator representations of HSS forms. Specifically, in the 2D case, we lay theoretical foundations and justify the existence of MHS structures based on the fast multipole method (FMM) and algebraic techniques such as representative subset selection. Rigorous numerical rank bounds and conditions for the structures are given. Representative subsets of points and a multi-layer tree are used to intuitively illustrate the structures. The MHS framework makes it convenient to explore multidimensional FMM structures. MHS representations are suitable for stable direct factorizations and can take advantage of existing methods and analysis well developed for simple HSS methods. Numerical tests for some discretized operators show that the appropriate inner-layer numerical ranks are significantly smaller than the off-diagonal numerical ranks used in standard HSS approximations.

In many applications one needs to process massive data of high dimensionality. In order to make data compact and reduce computational complexity, dimensionality reduction algorithms are commonly used. Linear discriminant analysis (LDA) is one of the most used approaches, which leads to a matrix trace ratio problem, i.e., maximization of the trace ratio $ρ(V)=Tr(V^TAV)/Tr(V^TBV)$, where $A$ and $B$ are $n×n$ real symmetric matrices with $B$ positive definite, and $V$ is an $n×p$ column orthonormal matrix. In this paper, we consider a commonly used Iterative Trace Ratio (ITR) algorithm developed by Ngo et al., $The$ $trace$ $ratio$ $optimization$ $problem$, $SIAM$ $Review$, $54 (3) (2012), pp. 545–569$. In implementations, it is common to use the symmetric Lanczos method to compute the $p$ eigenvectors of a certain large matrix corresponding to its $p$ largest eigenvalues at each iteration, and the resulting algorithm is abbreviated as ITR_L. We establish the global convergence and local quadratic convergence of the trace ratio itself. We then make two improvements over ITR_L: (i) using the refined Lanczos method to compute the desired eigenvectors at each iteration and (ii) providing a better initial guess via solving a generalized eigenvalue problem of the matrix pair $(A,B)$. The resulting algorithms are abbreviated as ITR_RL and ITR_GeigRL, respectively. Numerical experiments demonstrate that ITR_RL and ITR_GeigRL outperform ITR_L substantially.

Recent applications in the data science and wireless communications give rise to a particular Rayleigh-quotient maximization, namely, maximizing the sum-of-Rayleigh-quotients over a sphere constraint. Previously, it is shown that maximizing the sum of two Rayleigh quotients is related with a certain eigenvector-dependent nonlinear eigenvalue problem (NEPv), and any global maximizer must be an eigenvector associated with the largest eigenvalue of this NEPv. Based on such a principle for the global maximizer, the self-consistent field (SCF) iteration turns out to be an efficient numerical method. However, generalization of sum of two Rayleigh-quotients to the sum of an arbitrary number of Rayleigh-quotients maximization is not a trivial task. In this paper, we shall develop a new treatment based on the S-Lemma. The new argument, on one hand, handles the sum of two and three Rayleigh-quotients maximizations in a simple way, and also deals with certain general cases, on the other hand. Our result gives a characterization for the solution of this sum-of-Rayleigh-quotients maximization and provides theoretical foundation for an associated SCF iteration. Preliminary numerical results are reported to demonstrate the performance of the SCF iteration.

This paper is concerned with the way to find an optimal deflation for the eigenvalue problem associated with quadratic matrix polynomials. This work is a response of the work by Tisseur et al., $Linear$ $Algebra$ $Appl$., $435:464-479, 2011$, and solves one of open problems raised by them. We build an equivalent unconstrained optimization problem on eigenvalues of a hyperbolic quadratic matrix polynomial of order 2, and develop a technique that transforms the quadratic matrix polynomial to an equivalent one that is easy to solve. Numerical tests are given to illustrate several properties of the problem.

This paper is concerned with finding a minimum norm and robust solution to the partial quadratic eigenvalue assignment problem for vibrating structures by active feedback control. We present a receptance-based optimization approach for solving this problem. We provide a new cost function to measure the robustness and the feedback norms simultaneously, where the robustness is measured by the unitarity or orthogonalization of the closed-loop eigenvector matrix. Based on the measured receptances, the system matrices and a few undesired open-loop eigenvalues and associated eigenvectors, we derive the explicit gradient expression of the cost function. Finally, we report some numerical results to show the effectiveness of our method.

In this paper, we propose a new projected Newton iteration for computing the nonnegative Z-eigenpairs of nonnegative tensors. We show that the required iteration has a local quadratic convergence. More specially, the formulation aims to solve the tensor equation arising from the multilinear PageRank problem. Numerical experiments are provided to illustrate the effectiveness and superiority of the proposed approach.