Mengchu Xu

Mengchu Xu, Jian Wang, Yonina C. Eldar

Sparse Canonical Correlation Analysis (SCCA) is a fundamental statistical tool for identifying linear relationships in high-dimensional, multi-view data. While minimax theory establishes an optimal sample complexity scaling additively with the sparsity levels of the canonical vectors, computationally efficient algorithms typically suffer from a suboptimal multiplicative dependence. This computational-statistical gap is intrinsically tied to worst-case ``flat'' signal assumptions. In practice, however, multi-view signals frequently exhibit structured energy concentration, such as a power-law decay. To exploit this structural concentration and bypass the worst-case bottleneck, we propose Bilateral Spectral Energy Pursuit (Bi-SEP). Operating directly on the cross-covariance matrix, Bi-SEP is a stagewise adaptive algorithm that utilizes a proxy refinement step to dynamically track and capture cross-view signal energy. Theoretically, we establish a profile-adaptive sample complexity bound governed by the coupled energy profiles of the two views. Notably, under power-law decay models, we reveal a synergistic phase transition: the optimal linear sample complexity is attainable provided that the aggregate decay rate of the two views is sufficiently large. This result demonstrates that a highly concentrated signal in one view allows the model to accommodate a completely flat signal in its partner. Numerical experiments validate our theoretical findings, illustrating the advantages of Bi-SEP in structured, non-flat signal regimes.

Mengchu Xu, Yuxuan Zhang, Jian Wang

Sparse phase retrieval aims to recover a $k$-sparse signal from $m$ phaseless measurements. While the theoretically optimal sample complexity for successful recovery is $Ω(k \log n)$, existing algorithms can only achieve this bound for signals with specific structural assumptions, leading to a notable gap between theory and practice. To bridge this gap, we introduce an efficient initialization algorithm, termed generalized Exponential Spectral Pursuit (gESP). We prove that gESP can significantly expand the family of signals that are guaranteed to be recovered with the optimal sample complexity, thereby extending the scope of theoretical optimality to a much broader class of signals. Extensive simulations validate our theoretical findings and demonstrate that gESP consistently outperforms the state-of-the-art methods across diverse signal types.