PaperlayerView exact revision on arXiv

Source-linked AI summary

A generalized power iteration method for solving quadratic problem on the Stiefel manifold

Feiping Nie, Rui Zhang, Xuelong Li

arXiv:1701.00381v1cs.DS

TL;DR

The paper addresses quadratic optimization on the Stiefel manifold and related regression and Procrustes problems. It derives a generalized power iteration method with monotonic convergence to a local minimum and reports faster, more efficient empirical performance, especially for large data matrices.

  • Problem

    The paper studies the quadratic problem on the Stiefel manifold and its special cases, orthogonal least square regression and the unbalanced orthogonal Procrustes problem.

  • Method

    The paper derives a generalized power iteration method for QPSM and applies its theoretical convergence analysis to OLSR and UOPP.

  • Results

    The GPI method decreases the QPSM objective monotonically to a local minimum and converges faster with less CPU time, becoming more efficient for large data matrices.

  • Takeaways & Limitations

    GPI provides a general convergent approach for QPSM, OLSR, and UOPP, with empirical efficiency advantages that become more pronounced as data dimensions increase.

Abstract

from arXiv · show

In this paper, we first propose a novel generalized power iteration method (GPI) to solve the quadratic problem on the Stiefel manifold (QPSM) as min_{W^TW=I}Tr(W^TAW-2W^TB) along with the theoretical analysis. Accordingly, its special case known as the orthogonal least square regression (OLSR) is under further investigation. Based on the aforementioned studies, we then cast major focus on solving the unbalanced orthogonal procrustes problem (UOPP). As a result, not only a general convergent algorithm is derived theoretically but the efficiency of the proposed approach is verified empirically as well.

I. INTRODUCTION

The paper frames UOPP as an important but computationally demanding problem and introduces GPI to address these limitations while also solving the more general QPSM.

  • The OPP is a least-square problem on the Stiefel manifold that seeks an orthogonal rotation best fitting a hypothesis matrix.
  • Existing UOPP methods include EB, RSR, LSR, SP, and LR, using expanded objectives, iterative updates, projection, or Lagrangian multipliers.
  • These approaches involve complex, high-order procedures and deliberately initialized parameters, limiting their scope to UOPP rather than the general QPSM.
  • GPI is proposed for QPSM, with applications to OLSR and UOPP using a random initial guess and concise computational steps.
  • The paper reports that GPI converges with less CPU time and becomes more efficient for large-dimensional data matrices.

II. POWER ITERATION METHOD REVISITED

The revisited power iteration method extends from dominant-eigenvector computation to orthogonal iteration for multiple eigenvectors. Under positive semidefinite A, orthogonal iteration corresponds to a Stiefel-manifold trace optimization problem.

  • Power iteration repeatedly multiplies a randomly initialized vector by A and normalizes it to seek the dominant eigenvalue and eigenvector.
  • Orthogonal iteration extends power iteration to find the first k dominant eigenvalues and associated eigenvectors using repeated matrix multiplication and QR normalization.
  • Under positive semidefinite A, orthogonal iteration is equivalent to optimizing Tr(W^T A W) over orthonormal matrices.
  • The SVD-based power iteration updates W through M ← AW, compact SVD, and W ← UV^T, while preserving the objective value under orthogonal transformations.

III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD

The paper formulates QPSM over matrices with orthonormal columns and derives GPI by relaxing the objective with a positive-definite shifted matrix. Each iteration forms M, computes its compact SVD, and updates W through UV^T.

  • III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD: QPSM minimizes Tr(W^TAW−2W^TB) subject to W^TW=I_k on the Stiefel manifold.The Stiefel manifold consists of matrices with orthonormal columns.
  • III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD: The objective is relaxed using Ã=αI_m−A, where α is chosen so à is positive definite.The relaxation replaces the original quadratic term with an equivalent form suitable for the iterative derivation.
  • III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD: GPI initializes a random feasible W, computes M=2ÃW+2B, and solves a trace-maximization subproblem over the Stiefel manifold.The subproblem is solved by maximizing Tr(W^TM).
  • III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD: The trace-maximization update is W←UV^T, obtained from the compact SVD M=USV^T.The iteration repeats the matrix update and SVD-based retraction until convergence.
  • III. QUADRATIC PROBLEM ON THE STIEFEL MANIFOLD: GPI repeatedly performs the update until convergence, using a manifold retraction to preserve the Stiefel constraint.The paper identifies the SVD update as an instance of manifold retraction.

A. Theoretical analysis of GPI

Theoretical analysis shows that GPI decreases the QPSM objective monotonically and converges to a local minimum. Experiments further compare its convergence behavior with existing approaches and report convergence to the same objective value across random initializations.

  • A. Theoretical analysis of GPI: Positive definiteness of à yields a surrogate inequality that ensures each GPI iteration does not increase the QPSM objective.The proof uses a Cholesky factorization of Ã.
  • A. Theoretical analysis of GPI: GPI decreases the QPSM objective monotonically in every iteration until convergence.This is stated as Theorem 3.1.
  • A. Theoretical analysis of GPI: GPI converges to a local minimum of the QPSM problem because its limiting KKT condition matches that of the equivalent relaxed problem.The argument compares the KKT conditions after substituting the converged update.
  • A. Theoretical analysis of GPI: Experiments with many random initial guesses show uniform convergence to the same objective value, motivating a conjecture of global convergence.The paper presents this as a rational conjecture rather than a proved theorem.
  • A. Theoretical analysis of GPI: Under the same input data, EB, RSR, LSR, SP, LR, and GPI converge to the same objective value, while GPI converges faster during iteration.The comparison is reported for six approaches under three data matrices.

A. Orthogonal Least Square Regression

The paper reduces OLSR to the QPSM form by eliminating the unconstrained bias variable and identifying the resulting matrices. Consequently, Algorithm 1 can solve OLSR.

  • A. Orthogonal Least Square Regression: OLSR uses data matrix X, hypothesis matrix Y, regression matrix W, and an unconstrained bias vector b.The all-ones vector enters the bias-related expressions.
  • A. Orthogonal Least Square Regression: Optimizing with respect to b produces an expression involving n(Y^T1−W^TX1).This substitution removes the free bias variable from the formulation.
  • A. Orthogonal Least Square Regression: The reformulated OLSR objective has the exact same form as QPSM, with B=X^HY.This identifies the matrix term needed to apply the generalized power iteration method.
  • A. Orthogonal Least Square Regression: Because the reformulated OLSR is QPSM, OLSR can be solved using Algorithm 1.The reduction connects the regression problem directly to the proposed GPI solver.

B. Unbalanced Orthogonal Procrustes Problem

The paper defines balanced and unbalanced orthogonal Procrustes problems by the relationship between matrix dimensions. The unbalanced case has m>k, and the column-vector case reduces to LSQE.

  • B. Unbalanced Orthogonal Procrustes Problem: The balanced OPP is defined by m=k in the stated optimization formulation.This is the square-dimension case.
  • B. Unbalanced Orthogonal Procrustes Problem: The UOPP is defined by m>k.This is the dimensionally unbalanced case addressed by the paper.
  • B. Unbalanced Orthogonal Procrustes Problem: The paper begins expanding the balanced OPP formulation as a separate case when m=k.This follows the stated definition of the balanced problem.
  • B. Unbalanced Orthogonal Procrustes Problem: When Q is a column vector, corresponding to k=1, UOPP degenerates to the least square problem with a quadratic equality constraint.The resulting problem is called LSQE.

1) Balanced orthogonal procrustes problem revisited:

The balanced orthogonal Procrustes problem reduces to maximizing Tr(Q^T E^T G) under Q^TQ=I_k, yielding a closed-form analytical solution.

  • The balanced OPP has an analytical closed-form solution.
  • When m > k, the unbalanced OPP can be expanded into a quadratic objective under Q^TQ=I_k.

2) Unbalanced orthogonal procrustes problem:

UOPP is rewritten in the QPSM form, allowing GPI to solve it with monotonic convergence to a local minimum and greater generality than UOPP-specific approaches.

  • Setting A=E^TE and B=E^TG transforms UOPP into the exact QPSM form.
  • The resulting algorithm converges monotonically to a local minimum of UOPP and takes less time to converge than other approaches.
  • Unlike UOPP-specific approaches, GPI is designed for the more general QPSM.
  • GPI for UOPP initializes Q with Q^TQ=I_k and chooses γ so γI_m−E^TE is positive definite.
  • Each iteration updates M, computes its compact SVD M=USV^T, and sets Q←UV^T.

V. EXPERIMENTAL RESULTS

Experiments compare GPI with existing methods across parameter, CPU-time, matrix-dimension, and projection-method cases, reporting faster convergence and improved efficiency for larger problems.

  • Case 1: parameter dependence: Varying γ changes the convergence rate inversely but does not affect GPI's uniform convergence.
  • Case 2: CPU time comparison for solving UOPP: All compared UOPP methods converge to the same objective value, while GPI converges faster during iteration.
  • Case 2: CPU time comparison for solving UOPP: GPI has the lowest order of complexity and becomes more efficient as the number of data n increases.
  • Case 2: CPU time comparison for solving UOPP: GPI is the most efficient method under the square-matrix case.
  • Case 2: CPU time comparison for solving UOPP: LSR, SP, and RSR are less competitive than LR, EB, and GPI, with GPI's superiority becoming more apparent as dimension increases.
  • Case 3: CPU time comparison for solving LSQE: For LSQE, PMCT and GPI converge to the same objective value but follow different patterns, while GPI takes less time to converge.

VI. CONCLUDING REMARKS

The paper derives a generalized power iteration method for QPSM, with theoretical convergence support and empirical evidence of effectiveness and efficiency.

  • GPI decreases the QPSM objective value monotonically to a local minimum until convergence.
  • OLSR and UOPP are investigated as two special and significant cases of QPSM.
  • GPI takes less CPU time to converge to the optimal solution with a random initial guess, especially for large-dimensional data matrices.
Loading 1701.00381v1…