Search

Optimization over Stiefel manifolds has found wide applications in many scientific and engineering domains. Despite considerable research effort, high-dimensional optimization problems over Stiefel manifolds remain challenging, and the situation is exacerbated by nonsmooth objective functions. The purpose of this paper is to propose and study a novel coordinate-type algorithm for weakly convex (possibly nonsmooth) optimization problems over high-dimensional Stiefel manifolds, named randomized submanifold subgradient method (RSSM). Similar to coordinate-type algorithms in the Euclidean setting, RSSM exhibits low per-iteration cost and is suitable for high-dimensional problems. We prove that RSSM converges to the set of stationary points and attains $\varepsilon$-stationary points with respect to a natural stationarity measure in $\mathcal{O}(\varepsilon^{-4})$ iterations in both expectation and the almost-sure senses. To the best of our knowledge, these are the first convergence guarantees for coordinate-type algorithms to optimize nonconvex nonsmooth functions over Stiefel manifolds. An important technical tool in our convergence analysis is a new Riemannian subgradient inequality for weakly convex functions on proximally smooth matrix manifolds, which could be of independent interest.

The heteroscedastic probabilistic principal component analysis (PCA) technique, a variant of the classic PCA that considers data heterogeneity, is receiving more and more attention in the data science and signal processing communities. In this paper, to estimate the underlying low-dimensional linear subspace (simply called \emph{ground truth}) from available heterogeneous data samples, we consider the associated non-convex maximum-likelihood estimation problem, which involves maximizing a sum of heterogeneous quadratic forms over an orthogonality constraint (HQPOC). We propose a first-order method -- generalized power method (GPM) -- to tackle the problem and establish its \emph{estimation performance} guarantee. Specifically, we show that, given a suitable initialization, the distances between the iterates generated by GPM and the ground truth decrease at least geometrically to some threshold associated with the residual part of certain "population-residual decomposition". In establishing the estimation performance result, we prove a novel local error bound property of another closely related optimization problem, namely quadratic optimization with orthogonality constraint (QPOC), which is new and can be of independent interest. Numerical experiments are conducted to demonstrate the superior performance of GPM in both Gaussian noise and sub-Gaussian noise settings., Comment: 22 pages

This paper investigates the problem of exact community recovery in the symmetric $d$-uniform $(d \geq 2)$ hypergraph stochastic block model ($d$-HSBM). In this model, a $d$-uniform hypergraph with $n$ nodes is generated by first partitioning the $n$ nodes into $K\geq 2$ equal-sized disjoint communities and then generating hyperedges with a probability that depends on the community memberships of $d$ nodes. Despite the non-convex and discrete nature of the maximum likelihood estimation problem, we develop a simple yet efficient iterative method, called the \emph{projected tensor power method}, to tackle it. As long as the initialization satisfies a partial recovery condition in the logarithmic degree regime of the problem, we show that our proposed method can exactly recover the hidden community structure down to the information-theoretic limit with high probability. Moreover, our proposed method exhibits a competitive time complexity of $\mathcal{O}(n\log^2n/\log\log n)$ when the aforementioned initialization condition is met. We also conduct numerical experiments to validate our theoretical findings.

We focus on a class of non-smooth optimization problems over the Stiefel manifold in the decentralized setting, where a connected network of $n$ agents cooperatively minimize a finite-sum objective function with each component being weakly convex in the ambient Euclidean space. Such optimization problems, albeit frequently encountered in applications, are quite challenging due to their non-smoothness and non-convexity. To tackle them, we propose an iterative method called the decentralized Riemannian subgradient method (DRSM). The global convergence and an iteration complexity of $\mathcal{O}(\varepsilon^{-2} \log^2(\varepsilon^{-1}))$ for forcing a natural stationarity measure below $\varepsilon$ are established via the powerful tool of proximal smoothness from variational analysis, which could be of independent interest. Besides, we show the local linear convergence of the DRSM using geometrically diminishing stepsizes when the problem at hand further possesses a sharpness property. Numerical experiments are conducted to corroborate our theoretical findings., Comment: 27 pages, 6 figures, 1 table

Leading-edge (LE) noise is a common source of broadband noise for fans that can be suppressed using appended LE serrations. We conduct an integrated study of the morphological effects of interval, length, and inclination angle of owl-inspired LE serrations on the aeroacoustic characteristics of a mixed flow fan using experiments, computational fluid dynamics (CFD), and the Ffowcs Williams-Hawkings (FWH) analogy. A novel method for surface noise strength (SNS) visualization was developed based on the FWH analogy with large-eddy simulations, and a CFD-informed index SAPG is proposed to evaluate the severity of flow separation with pressure gradient, which are verified to be effective in examining the acoustic sources and chordwise separation. Acoustic measurements show the robust tradeoff solving capability of the serrations under various morphologies and the SNS visualizations indicate that the separation-induced LE noise is suppressed considerably. One-third octave analyses suggest that extending serration length can lower separation noise more effectively than shrinking the interval over 100-3k Hz. A smaller interval is more desirable while an optimal length exists in association with tonal noise. Moreover, small inclination angles (below 20 degrees) enable the deceleration of oncoming flows with stagnation relieved, and consequently, further suppress the LE noise, by a flow-buffering effect. Heavy inclination angles (over 40 degrees) induce an additional tip vortex, causing high-coherence turbulence impingement noise and resulting in a drastic increase in broadband noise at frequencies exceeding 4k Hz. Our study thus clarifies the morphological effects of LE serrations on aeroacoustic signatures of rotary devices while providing useful methods for acoustic analyses., Comment: 43 pages, 17 figures

Group synchronization refers to estimating a collection of group elements from the noisy pairwise measurements. Such a nonconvex problem has received much attention from numerous scientific fields including computer vision, robotics, and cryo-electron microscopy. In this paper, we focus on the orthogonal group synchronization problem with general additive noise models under incomplete measurements, which is much more general than the commonly considered setting of complete measurements. Characterizations of the orthogonal group synchronization problem are given from perspectives of optimality conditions as well as fixed points of the projected gradient ascent method which is also known as the generalized power method (GPM). It is well worth noting that these results still hold even without generative models. In the meantime, we derive the local error bound property for the orthogonal group synchronization problem which is useful for the convergence rate analysis of different algorithms and can be of independent interest. Finally, we prove the linear convergence result of the GPM to a global maximizer under a general additive noise model based on the established local error bound property. Our theoretical convergence result holds under several deterministic conditions which can cover certain cases with adversarial noise, and as an example we specialize it to the setting of the Erd\"os-R\'enyi measurement graph and Gaussian noise.

In this paper, we aim at solving the cardinality constrained high-order portfolio optimization, i.e., mean-variance-skewness-kurtosis model with cardinality constraint (MVSKC). Optimization for the MVSKC model is of great difficulty in two parts. One is that the objective function is non-convex, the other is the combinational nature of the cardinality constraint, leading to non-convexity as well dis-continuity. Based on the observation that cardinality constraint has the difference-of-convex (DC) property, we transform the cardinality constraint into a penalty term and then propose three algorithms including the proximal difference of convex algorithm (pDCA), pDCA with extrapolation (pDCAe) and the successive convex approximation (SCA) to handle the resulting penalized MVSK (PMVSK) formulation. Moreover, theoretical convergence results of these algorithms are established respectively. Numerical experiments on the real datasets demonstrate the superiority of our proposed methods in obtaining high utility and sparse solutions as well as efficiency in terms of time usage., Comment: ICASSP 2021