source/sections/problem_setup.tex

% \newpage
\section{Problem Setup}\label{sec:formulation}

We study principal eigenvector estimation in a streaming setting where samples \mbox{$\vv_t \sim \mathcal{N}(\vzero, \mSigma)$} arrive sequentially and cannot be stored. Instead of observing the full vector $\vv_t \in \R^d$, we obtain only two linear measurements \mbox{$\vx_t = \mA_t\vv_t$} where \mbox{$\mA_t \in \R^{2 \times d}$}. The challenge is to recover the principal eigenvector $\bar\vu$ from these compressed measurements using only the current sample and estimate $\vu_t$ at each iteration.

When the measurement matrices $\mA_t$ are chosen randomly and independently of the current estimate, they are generally misaligned with both the true principal eigenvector and the current estimate $\vu_t$. This misalignment introduces a critical challenge: randomly oriented measurements provide limited information about the signal direction. When data is drawn from a covariance matrix $\mSigma$ with leading eigenvalue $\lambda_1$ much larger than trailing eigenvalues $\lambda_2, \ldots, \lambda_d$, most of the variance lies along the principal eigenvector $\bar\vu$. Random measurements, however, capture a mixture of signal (the principal component) and noise (the trailing eigenspace), with no guarantee that the signal component is well-represented. This becomes particularly severe in high dimensions when random measurement vectors $\mA_t$ are nearly orthogonal to the principal direction $\bar\vu$.

Adaptive sensing addresses this limitation by designing the measurement matrix $\mA_t$ based on the current estimate $\vu_t$. A natural approach would measure only along the current estimate, i.e., setting $\mA_t = \vu_t^T$. However, this would only reinforce our current estimate without capturing information from orthogonal directions needed to correct errors or track changes. The key insight is to balance exploitation (measuring along $\vu_t$) with exploration (measuring in a direction orthogonal to $\vu_t$), ensuring both signal amplification and sufficient exploration to enable convergence.

% \newpage
\subsection{Algorithm}

\begin{algorithm}[t]
\caption{Compressive Oja's, Rank One, Adaptive Sensing}
\label{alg:oja_comp}
\begin{algorithmic}[1]
\STATE \textbf{Initialize}: $\vu_0\in\R^d, \|\vu_0\|_2 = 1$
\STATE \textbf{Step Size}: $\eta_t > 0$
\FOR{$t\in 1\hdots T$}
    \STATE \textbf{Draw sample:} $\vv_t\in\R^d\sim \mathcal{N}(\vzero, \mSigma)$
    \STATE \textbf{Draw random unit vector:} \\$\vb_t\in\R^d, \|\vb_t\|_2=1, \vb_t\perp \vu_t$
    \STATE \textbf{Compressive measurement:} \\$\vx_t=\mA_t\vv_t=[\vu_t^T\vv_t; \vb_t^T\vv_t]$
    \STATE \textbf{Update eigenvector:} \\$\hat \vu_{t+1} = \vu_t + \eta_t (\vu_t\vu_t^T + \vb_t\vb_t^T) \vv_t \vv_t^T \vu_t$
    \STATE \textbf{Normalize:} $\vu_{t+1}=\hat \vu_{t+1}/\|\hat \vu_{t+1}\|_2$
\ENDFOR
\STATE \textbf{Return} $\vu_T$
\end{algorithmic}
\end{algorithm}

We focus on estimating the leading eigenvector $\bar\vu$ of the covariance matrix using only two measurements per iteration, i.e., $\mA_t \in \R^{2 \times d}$. Given a current eigenvector estimate $\vu_t$, we use the adaptive sampling scheme proposed in \cite{ongie_enhanced_2017} which chooses:
\begin{align*}
\mA_t=\begin{bmatrix}
    \vu_t^T \\ \vb_t^T
\end{bmatrix}
\quad\quad
\vx_t=\mA_t\vv_t
\end{align*}
where $\vb_t$ is a unit vector drawn randomly from the orthogonal complement of $\vu_t$. $\vb_t$ can be constructed by taking \mbox{$\hat \vb_t\sim \mathcal{N}(0, \mId-\vu_t\vu_t^T)$} and normalizing \mbox{$\vb_t=\hat \vb_t / \|\hat \vb_t\|_2$}.

We assume normally distributed data with arbitrary covariance \mbox{$\vv_t\sim\mathcal{N}(\vzero, \mSigma)$}. We denote the principal eigenvector of $\mSigma$ as $\bar\vu$, its eigenvalues as \mbox{$\lambda_1>\lambda_2\geq\lambda_3\geq \dots\geq\lambda_d$}, and its eigengap as \mbox{$\Delta=\lambda_1-\lambda_2$}. Importantly, our formulation treats ``noise'' as part of the data-generating distribution (the trailing eigenspace) rather than additive measurement corruption --- the leading eigenvector $\bar\vu$ represents the ``signal'' direction we aim to estimate.

\begin{remark}[Connection to Spiked Covariance Model]
Our eigenvalue formulation generalizes the classical \emph{spiked covariance model} \mbox{$\vv_t = \bar\vu s_t + \ve_t$} with \mbox{$s_t \sim \mathcal{N}(0,1)$} and \mbox{$\ve_t \sim \mathcal{N}(\vzero, \sigma^2\mId)$}, which yields \mbox{$\mSigma = \bar\vu\bar\vu^T + \sigma^2\mId$} with $\lambda_1 = 1 + \sigma^2$, $\lambda_2 = \sigma^2$, and $\Delta = 1$. Our formulation also handles arbitrary covariance structures with multiple distinct trailing eigenvalues.
\end{remark}

The algorithm update in line 7 of Algorithm~\ref{alg:oja_comp} can be derived from the Adaptive GROUSE framework \cite{ongie_enhanced_2017} by imputing the high-dimensional observation from compressed measurements (see Appendix~\ref{sec:imputation} for details). The imputed data simplifies to the projection \mbox{$\tilde\vv_t = (\vu_t\vu_t^T + \vb_t\vb_t^T)\vv_t$}, which is then used in the standard Oja update. The key innovation of our work is \emph{not} the algorithm design itself, but rather the \emph{proof technique} used to establish convergence guarantees in the noisy setting. Beyond the upper bound, we contribute three additional novel results: (i) a new Assouad-based proof of the classical \mbox{$\Omega(\lambda_1\lambda_2 d/(\Delta^2 t))$} lower bound for fully-observed PCA, providing an alternative to existing information-theoretic arguments; (ii) the first \mbox{$\Omega(\lambda_1\lambda_2 d^2/(\Delta^2 t))$} lower bound for compressed PCA, proving that the $d^2$ factor in our upper bound is optimal; and (iii) fixed-point analysis characterizing the steady-state tracking error when the principal eigenvector drifts over time.