- Rating
- 2
- Confidence
- 3
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper studies uniform spectral bounds for covariance matrices formed from arbitrary, potentially data-dependent subsets of random vectors. For i.i.d. Gaussian vectors, it derives simultaneous lower and upper bounds on the extreme eigenvalues in terms of trimmed Gaussian second moments, together with complementary constructions establishing limiting tightness.
The framework is further extended to sub-Gaussian vectors under additional assumptions and to stationary geometrically strong-mixing Gaussian sequences, where a uniform lower spectral bound is obtained. Applications to K-subspace clustering and Gaussian robust regression are also presented.
Critical strengths
-
Well-motivated problem setting: The paper addresses an issue that arises when the selected subset depends on the same data used to form the covariance matrix. The simultaneous nature of the bounds makes them applicable to optimization with data-dependent selection.
-
Coherent theoretical framework and presentation: The Gaussian bounds are expressed through explicit trimmed-moment curves and accompanied by complementary tightness constructions. The progression from i.i.d. Gaussian data to sub-Gaussian and temporally dependent observations, followed by applications, gives the paper a clear overall structure.
Critical weaknesses
-
Limited novelty of the main Gaussian result relative to prior work: Han and Xu already establish the correct scaling for the lower spectral coefficient under arbitrary erasures, with better small- sample dependence. The present paper contributes explicit trimmed-moment curves and limiting tightness constructions, but it is not clear to me that these refinements constitute a sufficiently substantial advance over the existing correct-order results.
-
The experimental section appears incomplete. Appendix D explicitly states that the parameter reconciliation is pending and that the reported experiment has not yet been verified. In addition, the reported SNR values appear inconsistent with the stated subspace affinity.
Questions for authors
-
Beyond providing the explicit curves, what substantive gain does the main theorem provide over existing results with the correct scaling? Are the exact curves essential for any of the applications?
-
It would be helpful to add citations directly when introducing the LRGMM and the K-subspace formulation, rather than only discussing related work later.
4 comments
Dear Reviewer HQf9,
We would like to once again sincerely thank you for your time and thoughtful feedback on our work.
As we approach the end of the rebuttal discussion period, we would appreciate hearing whether our response has addressed your concerns. We would also be happy to address any further questions or concerns whenever your schedule permits.
Thank you again for your time and consideration.
Authors
Thanks for the detailed responses. I see how the revision improves the sample complexity over Han and Xu. Since Haddock et al. already get the dependence up to log factors under their assumptions, my understanding is that the main contribution here is pinning down the exact limiting gaussian curve for the worst-case lower bound. That still feels incremental to me.
As you point out, a cubic lower bound is enough to get the clustering rate. Is there a setting where using the exact curve (beyond the same asymptotic sample complexity of Haddock et al.) changes what you can guarantee? That would help me see how much the extra precision matters. For now, I'd keep my original score.
Exact Gaussian curves yield concrete algorithmic guarantees
Thank you for this follow-up. We agree that Haddock et al. already established the same asymptotic sample complexity, and that a cubic lower bound suffices for our clustering rate. The precise curves also enlarge the corruption range for which existing algorithms can be certified to converge in the following setting.
Robust regression: an explicit comparison of corruption thresholds.
Consider Gaussian covariates with arbitrary sparse response corruption:
x_i\overset{\mathrm{i.i.d.}}{\sim}\mathcal N(0,I_d),\qquad \|c\|_0\le\beta M.$$ The corruption support and values may depend on the data. TORRENT-FC [1] alternates least squares with retaining the $(1-\beta)M$ smallest residuals. With no additional dense noise, its deterministic theorem guarantees geometric convergence and exact recovery when $$(1+\sqrt2)\frac{\Lambda_\beta}{\lambda_{1-\beta}}<1,$$ where $\lambda_\kappa=\min_{|S|=\kappa M}\lambda_{\min}(\sum_{i\in S}x_ix_i^\top)$ and $\Lambda_\beta=\max_{|T|=\beta M}\lambda_{\max}(\sum_{i\in T}x_ix_i^\top)$. Our uniform bounds and complementary constructions give, in probability as $M\to\infty$ with fixed $d$, $$\lambda_{1-\beta}/M\to b(1-\beta),\qquad \Lambda_\beta/M\to u(\beta),$$ where $$b(\kappa)=\kappa-2q_\kappa\phi(q_\kappa),\qquad q_\kappa=\Phi^{-1}((1+\kappa)/2),\qquad u(\beta)=1-b(1-\beta).$$ Here $\phi,\Phi$ are the standard Gaussian density and distribution function. The limiting convergence condition becomes $$r(\beta)=(1+\sqrt2)\frac{u(\beta)}{b(1-\beta)}<1.$$ The table compares the original guarantee with substitutions into this same criterion. The last three rows use the same exact upper coefficient $u(\beta)$; their thresholds are computed in the large-sample limit. | Spectral analysis | Lower coefficient $\quad$ | Threshold| |---|---|---:| | Original Gaussian guarantee [1, Theorem 4] | Estimates in [1] | $1.54\\%$ | Gaussian specialization of Haddock et al.'s lower-bound proof [2] \$\quad \$ | $(\pi/288)(1-\beta)^3$ | $0.03\\%$ | | Strongest universal cubic lower bound [3, Eq. (0.9)] | $(\pi/6)(1-\beta)^3$ | $3.07\\%$ | | **Our exact Gaussian curves** | $b(1-\beta)$ | **$5.36\\%$** | The [2] row is our substitution of its spectral bound into TORRENT's criterion: squaring the factor $1/(24D)$ in Proposition 1 and specializing its proof to Gaussian rows, with $D=1/\sqrt{2\pi}$ and consistent scaling, gives $\pi/288$. The universal bound $b(\kappa)\ge(\pi/6)\kappa^3$ follows by applying [3, Eq. (0.9)] to $h(x)=\phi(x)\mathbf 1_{\{|x|\le q_\kappa\}}$. Its constant is optimal because $b(\kappa)/\kappa^3\to\pi/6$ as $\kappa\downarrow0$. Our threshold follows from $$u(\beta)<\frac{1}{2+\sqrt2},\qquad \beta<\beta_\star,\quad \beta_\star\approx0.05364712.$$ **Thus the certified range increases from the original $1.53846\%$ to $5.36471\%$, and exceeds the $3.06748\%$ achievable even with the optimal universal cubic coefficient.** These are sufficient convergence thresholds for the existing algorithm. **Finite sample** Take $\beta=0.04$, $d=10$, $M=6.4\times10^6$, $\eta_L=0.01$, $\eta_U=0.0375$. Our Theorems 1–2 yield $$\lambda_{0.96}/M\ge0.99^2b(0.9504)>0.708062,\quad \Lambda_{0.04}/M\le1.0375^2u(0.0415)<0.263889$$ with probability $>0.99979$. Hence $(1+\sqrt2)\Lambda_{0.04}/\lambda_{0.96}<0.9$, guaranteeing linear convergence of TORRENT-FC for every $\|c\|_0\le0.04M$, which is still higher than both the original and the strongest universal cubic lower bound. [1] Bhatia, Jain, and Kar. *Robust Regression via Hard Thresholding*. NeurIPS 2015, Theorems 3–4. [2] Haddock, Needell, Rebrova, and Swartworth. *Quantile-based Iterative Methods for Corrupted Systems of Linear Equations*. SIAM J. Matrix Anal. Appl. 43(2):605–637, 2022, Proposition 1. [3] Bobkov, S. G. and Chistyakov, G. P. and G{\"o}tze, F. Bounds for characteristic functions in terms of quantiles and entropy. Electronic Communications in Probability, 17, 1--9, 2012. ```
Thank you for these comments. We have revised the manuscript; the corresponding changes are marked in blue.
We have sharpened Theorem 1 from the submitted κ−6 sufficient sample dependence to κ−1, up to logarithms, while preserving the lower spectral coefficient. Section 2.1 (Eqs. (7)–(8)) now states
M≳ηκ−1[mlog(Cη/κ)+log(1/ρ)]
for fixed slack 0<η<1/2. This improvement concerns sample complexity and is distinct from the already known κ3 order of the lower spectral coefficient. Under the same Gaussian model and normalization, Han and Xu's full-sparsity specialization of Corollary 1.6 gives the sufficient condition M≳κ−3[m+log(1/ρ)]. We have updated this quantitative comparison in Section 2.1 and Appendix A.
The new Lemma 1 in Appendix F.1 sets p=(1−η)κ, Y=Z21{∣Z∣≤qp}, Z∼N(0,1), qp=Φ−1((1+p)/2), and μ=EY=b(p). It proves EY2≤3μ2/p, hence
\le e^{-\eta^2pM/6}.$$ Appendix F.2 derives the new sample bound using the existing net argument, preserving $(1-\eta)^2b((1-\eta)\kappa)$. The downstream clustering sample condition has also been updated in Theorem 5, Eq. (30). We have added Haddock et al., *Quantile-based Iterative Methods for Corrupted Systems of Linear Equations* (2022), and explicitly acknowledged that its Proposition 1 already achieves inverse-fraction sample dependence under its assumptions (Section 2.1; Appendix A). We claim the full central/tail curves and complementary limiting constructions together with the refined finite-sample lower guarantee, without claiming the inverse-fraction order itself as new. > **2. Role of the exact curves.** The order-level clustering guarantee only needs $b(\tau)\ge c\tau^3$; Appendix H.5 derives the retained conservative SNR rate from this bound. The full curve enters the explicit recovery thresholds in Theorem 5, Eqs. (27)–(30). Appendix D now evaluates these thresholds numerically. We have also specified the Gaussian concentration constants and added a separately calibrated spectral example with confidence exceeding $0.999$ (Section 2.1, Eq. (15); Appendix B.1). The original figures remain coefficient illustrations. > **3. Experimental validity and SNR.** We have replaced the unverified Appendix D table with a new experiment and explicit condition checks. Revised Theorem 5 applies to every feasible candidate satisfying $\widehat F\le F^\star+\Delta$, where $F^\star$ is the objective at the true model. The bound $S\le4W+2\Delta$, with noiseless residual $S$ and total noise energy $W$, removes the original Assumption 1's dimension restriction (Appendices H.3 and H.5). Thus this validation no longer requires a global-optimality certificate. The new experiment uses $K=2,n=4,d=1$, $N_1=N_2=10{,}000$, affinity $0.67$, and noise standard deviation $0.002$, giving the consistent SNR $(1-0.67^2)/0.002=275.55$. With $\tau=1/4$ and $\rho=0.001$, the sample requirement is $8697.47<10{,}000$, the separation inequality is $5.220786<10.819533$, and the analytic failure bound is below $0.000520$. All 100 outputs satisfy $\widehat F\le F^\star$; mean/max errors are $0.17065\%/0.25\%$, versus the conservative $25\%$ bound (Appendix D, Table 1). Fitting uses only unlabeled observations. Appendix D reports the initialization, seeds, and condition checks, and clarifies that confidence is per dataset. This controlled high-SNR experiment establishes applicability, without establishing general algorithmic superiority; the objective comparison uses simulation truth. > **4. First-use citations.** We have added citations directly at the LRGMM introduction (Section 4) and the K-subspaces formulation (Section 4.1, Eq. (23)).