acceptodds
Under review as a conference paper at ICLR 2027

Provably Identifying Linear Constraints under Unknown and Singular Measurement Noise

Abstract

Many scientific and engineering systems satisfy unknown linear relations, but only noisy measurements of their variables are available. Four issues make these relations challenging. Noise variances can differ across variables, measurement errors can be correlated, and the noise covariance matrix can be singular. Moreover, both the noise covariance matrix and the number of relations may be unknown. We address all four challenges by proposing a novel generalized eigenvalue decomposition (GenEVD) based algorithm that avoids inverting the noise covariance matrix unlike existing methods. Iterative PCA and ordinary least squares arise as special cases of our method. Our first algorithm alternates this spectral update with an identifiable supported-moment estimator of the noise covariance. Our second algorithm estimates the number of relations through a descending unity-eigenvalue test. We establish high-probability recovery of the constraint subspace, noise covariance matrix, and number of relations. We also prove local geometric convergence and obtain a subspace rate with minimax-optimal dependence on sample size and dimension. Controlled synthetic experiments and empirical study on seven real-world datasets validate the corresponding theoretical claims.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
generalized eigenvalue decomposition, subspace recovery, PCA, SVD

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_7AQROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies the problem of recovering linear relation Ax=0Ax=0 using noisy measurements xx with unknown noise covariance Σ\Sigma which may be non-diagonal and/or singular. It proposes a method GenEVD, which covers IterativePCA and OLS as special cases, where the key steps are alternating between a solving a generalized eigenvector problem, and updating the estimate of Σϵ\Sigma_\epsilon. Theoretical results on finite-sample error bounds are provided. Experiment results are shown on datasets with synthetic noise injections.

Critical strengths
  • The proposed GenEVD method provides a promising improvement over the widely used IPCA, with statistical guarantees.
  • The theoretical analysis is solid and of interest to the community. In particular, Theorem 8 provides an end-to-end recovery bound for the proposed algorithm and greatly enhances the rigor of the proposed method. The proof is correct as far as I could check.
Critical weaknesses
  • All numerical simulation results shown are on datasets with synthetic Gaussian noise. The real data experiment does not directly use the raw dataset, but first preprocess it by projection into low-rank. While this serves its purpose of demonstrating theoretical results, it's still valuable and important to understand how the proposed method performs on real data, e.g. how well it can handle sparse noise and data that are not perfectly low rank.
Questions for authors
  • Can you provide simulation results on real-world datasets, compared with other baseline methods? At the minimum you can create synthetic experiments to test the sensitivity of performance to data suboptimality patterns (e.g. sparse noise, non-perfect low rank), but real data experiments are still valuable.
  • Minor: GenEVD has not been defined before Lemma 1, which already references it. Can you reorganize the flow or reword Lemma 1 to make this clearer?
4 comments
AuthorsOpenReview ↗

Rebuttal 1/n

We thank the reviewer for checking the proof and for the constructive comments. We have conducted new experiments with non-Gaussian noise distributions, outliers, and approximately low-rank data, as requested by the reviewer.

We also summarize the new experiments conducted for Reviewer 6waE; the details are in our response to that reviewer.

  • Initialization (Tables R1–R3). From six starts, including random ones, GenEVD reached the same estimate in every run.

  • Number of relations (Table R4). Compared with thresholding the spectrum of Sy\mathbf{S}_y, our method never returned a wrong mm, including Example A, where thresholding was wrong in every trial.

  • OLS given the noise-free variables (Table R5). GenEVD coincides with OLS when only the response is noisy, and recovers the coefficients when a predictor is also noisy, where OLS is biased.

  • Larger dimensions (Table R6). At d=50d=50 and d=100d=100, GenEVD achieves a lower error than the other methods.

We kindly request the reviewer to let us know if they have any further questions.


This paper studies the problem of recovering linear relation Ax=0Ax=0 using noisy measurements xx with unknown noise covariance Σ\Sigma which may be non-diagonal and/or singular. It proposes a method GenEVD, which covers IterativePCA and OLS as special cases, where the key steps are alternating between a solving a generalized eigenvector problem, and updating the estimate of Σϵ\Sigma_\epsilon. Theoretical results on finite-sample error bounds are provided. Experiment results are shown on datasets with synthetic noise injections.

A: We thank the reviewer for the summary. In continuation, the method also estimates the number of relations mm by counting the generalized eigenvalues equal to one (Algorithm 2), with a guarantee (Theorem 6).


The proposed GenEVD method provides a promising improvement over the widely used IPCA, with statistical guarantees.

A: We appreciate the reviewer’s recognition. GenEVD coincides with IPCA when Σϵ≻0\mathbf{\Sigma}_{\epsilon}\succ0 (Lemma 1), and it still applies when some variables are noise-free, where IPCA is undefined.


The theoretical analysis is solid and of interest to the community. In particular, Theorem 8 provides an end-to-end recovery bound for the proposed algorithm and greatly enhances the rigor of the proposed method. The proof is correct as far as I could check.

A: We sincerely thank the reviewer for checking the proof.


Our method performs better on synthetic datasets for non-gaussian noise or outliers or approximate low rank

All numerical simulation results shown are on datasets with synthetic Gaussian noise. The real data experiment does not directly use the raw dataset, but first preprocess it by projection into low-rank. While this serves its purpose of demonstrating theoretical results ... it can handle sparse noise and data that are not perfectly low rank.

A: We thank the reviewer for this constructive comment. We ran experiments with non-Gaussian noise distributions, outliers, and approximately low-rank data, and observed that GenEVD remains accurate. The setup, results, and inference are presented below.

  • Setup. Case Study 1 (d=5d=5, m=3m=3) with s=1s=1 noise-free variable, 50 trials, all baselines of Table 2. We change one aspect of the data at a time:

    • Noise distribution (Table R9): the entries of the standardized noise follow the uniform, Rademacher, Laplace or Student-t5t_5 distribution, with the same covariance Σϵ\mathbf{\Sigma}_{\epsilon}.

    • Outliers (Table R10): ±10\pm10 noise standard deviations on a fraction p=0.1p=0.1 of the entries of the noisy variables, on top of the dense noise. This is the sparse noise mentioned by the reviewer.

    • Approximate low rank (Table R11): Σx=Σx′+ξPC\mathbf{\Sigma}_x=\mathbf{\Sigma}_x'+\xi\mathbf{P}_{\mathcal{C}} with ξ=0.01,σC2\xi=0.01\\,\sigma_{\mathcal{C}}^2, so the relations hold only up to a residual variance ξ\xi.

  • Metric. θmax⁡\theta_{\max} (degrees) between the estimated and the true constraint subspaces, as in Table 2; lower is better.

Table R9: Our proposed method outperforms others for non-Gaussian noise (synthetic data).

Noise distributionnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Uniform500014.0±0.814.0 \pm 0.83.3±0.33.3 \pm 0.33.3±0.33.3 \pm 0.34.2±1.24.2 \pm 1.260.8±19.960.8 \pm 19.989.5±0.389.5 \pm 0.30.4±0.2\mathbf{0.4 \pm 0.2}
Rademacher500014.2±0.714.2 \pm 0.73.3±0.33.3 \pm 0.33.4±0.33.4 \pm 0.35.0±1.85.0 \pm 1.860.8±19.960.8 \pm 19.989.6±0.289.6 \pm 0.20.4±0.1\mathbf{0.4 \pm 0.1}
Laplace500014.0±0.814.0 \pm 0.83.3±0.33.3 \pm 0.33.2±0.33.2 \pm 0.32.5±0.82.5 \pm 0.860.8±19.960.8 \pm 19.989.6±0.389.6 \pm 0.30.4±0.2\mathbf{0.4 \pm 0.2}
Student-t5t_5500014.1±0.814.1 \pm 0.83.3±0.33.3 \pm 0.33.1±0.33.1 \pm 0.32.6±0.52.6 \pm 0.556.8±24.356.8 \pm 24.389.6±0.489.6 \pm 0.40.4±0.2\mathbf{0.4 \pm 0.2}
AuthorsOpenReview ↗

Rebuttal 2/n

Table R10: Our proposed method outperforms others under outliers (synthetic data).

nnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
50087.3±5.587.3 \pm 5.557.8±17.257.8 \pm 17.243.7±16.243.7 \pm 16.28.4±11.68.4 \pm 11.668.3±8.968.3 \pm 8.986.2±2.486.2 \pm 2.44.5±2.0\mathbf{4.5 \pm 2.0}
200089.1±0.789.1 \pm 0.762.2±16.462.2 \pm 16.450.5±17.350.5 \pm 17.39.2±11.19.2 \pm 11.167.8±9.767.8 \pm 9.787.8±1.687.8 \pm 1.62.4±0.9\mathbf{2.4 \pm 0.9}
500089.4±0.489.4 \pm 0.464.7±16.164.7 \pm 16.154.2±16.854.2 \pm 16.86.4±6.16.4 \pm 6.163.0±18.063.0 \pm 18.088.6±1.088.6 \pm 1.01.5±0.6\mathbf{1.5 \pm 0.6}

Table R11: Our proposed method outperforms others when the signal covariance is approximately low rank (synthetic data).

nnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
50015.0±1.515.0 \pm 1.53.5±0.73.5 \pm 0.73.0±0.73.0 \pm 0.73.7±1.13.7 \pm 1.164.1±16.064.1 \pm 16.088.7±0.988.7 \pm 0.91.5±0.5\mathbf{1.5 \pm 0.5}
200014.9±1.214.9 \pm 1.23.5±0.43.5 \pm 0.43.4±0.43.4 \pm 0.43.8±1.03.8 \pm 1.063.8±15.863.8 \pm 15.889.4±0.589.4 \pm 0.50.9±0.3\mathbf{0.9 \pm 0.3}
500015.2±0.715.2 \pm 0.73.4±0.33.4 \pm 0.33.3±0.33.3 \pm 0.33.7±1.13.7 \pm 1.167.3±0.767.3 \pm 0.789.6±0.489.6 \pm 0.40.8±0.2\mathbf{0.8 \pm 0.2}

Inference.

  • Non-Gaussian noise distributions (Table R9): the error of GenEVD is 0.4∘0.4^\circ for every distribution, the same as for Gaussian noise (Table 2, s=1s=1, n=5000n=5000), and it remains lower than that of the other methods.

  • Outliers with p=0.1p=0.1 (Table R10): GenEVD performs better than the other methods at every nn.

  • Approximately low-rank signal covariance with ξ=0.01,σC2\xi=0.01\\,\sigma_{\mathcal{C}}^2 (Table R11): we make a similar observation at every nn.


Our method performs better on real-world datasets for non-gaussian noise or outliers or approximate low rank

Can you provide simulation results on real-world datasets, compared with other baseline methods? At the minimum you can create synthetic experiments to test the sensitivity of performance to data suboptimality patterns (e.g. sparse noise, non-perfect low rank), but real data experiments are still valuable.

A:

Real-world datasets. We repeat these experiments on the seven real-world datasets of Table 3, with the same rank-two projection, noise covariance, support and samples, and change one aspect at a time. We report the largest nn of each dataset.

  • Non-Gaussian noise distributions (Tables R12–R15: uniform, Rademacher, Laplace and Student-t5t_5) and outliers with p=0.1p=0.1 (Table R16) are generated as above.

  • Approximate low rank (Table R17): the signal is Prefx+η,PCx\mathbf{P}_{\mathrm{ref}}\mathbf x+\eta\\,\mathbf{P}_{\mathcal{C}}\mathbf x, where Prefx\mathbf{P}_{\mathrm{ref}}\mathbf x is the rank-two projection of the real data x\mathbf x and PCx\mathbf{P}_{\mathcal{C}}\mathbf x is the real component removed by it. We choose η\eta so that ξ=η2∥PCΣrealPC∥op\xi=\eta^2\Vert \mathbf{P}_{\mathcal{C}}\mathbf{\Sigma}_{\mathrm{real}}\mathbf{P}_{\mathcal{C}}\Vert _{\mathrm{op}} gives ξ/σC2=0.01\xi/\sigma_{\mathcal{C}}^2=0.01.

Table R12: Our proposed method outperforms others for uniform noise on real-world datasets.

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76816.7±0.716.7 \pm 0.713.7±0.313.7 \pm 0.314.0±0.314.0 \pm 0.316.0±0.716.0 \pm 0.780.4±4.880.4 \pm 4.812.8±0.412.8 \pm 0.41.6±0.7\mathbf{1.6 \pm 0.7}
Air Quality899156.2±3.656.2 \pm 3.641.6±0.841.6 \pm 0.841.8±0.941.8 \pm 0.939.3±4.339.3 \pm 4.389.7±0.189.7 \pm 0.151.6±0.551.6 \pm 0.50.6±0.2\mathbf{0.6 \pm 0.2}
Appliances1973513.0±0.213.0 \pm 0.220.0±0.420.0 \pm 0.420.5±0.420.5 \pm 0.438.0±9.538.0 \pm 9.586.1±0.286.1 \pm 0.250.5±0.550.5 \pm 0.50.5±0.2\mathbf{0.5 \pm 0.2}
Gas Drift139109.9±0.19.9 \pm 0.19.0±0.29.0 \pm 0.29.2±0.29.2 \pm 0.212.2±0.812.2 \pm 0.876.6±0.476.6 \pm 0.413.4±0.213.4 \pm 0.20.4±0.2\mathbf{0.4 \pm 0.2}
MHEALTH1000013.1±0.213.1 \pm 0.29.5±0.29.5 \pm 0.29.5±0.29.5 \pm 0.210.6±0.410.6 \pm 0.463.2±0.163.2 \pm 0.178.2±0.378.2 \pm 0.30.4±0.1\mathbf{0.4 \pm 0.1}
Power Plant956830.2±0.230.2 \pm 0.221.7±0.421.7 \pm 0.421.9±0.421.9 \pm 0.422.9±8.922.9 \pm 8.987.7±0.687.7 \pm 0.671.2±0.571.2 \pm 0.50.5±0.2\mathbf{0.5 \pm 0.2}
Household2000018.1±0.318.1 \pm 0.313.2±0.413.2 \pm 0.413.6±0.413.6 \pm 0.448.6±24.748.6 \pm 24.775.8±0.675.8 \pm 0.684.9±1.584.9 \pm 1.50.3±0.2\mathbf{0.3 \pm 0.2}
AuthorsOpenReview ↗

Rebuttal 3/n

Table R13: Our proposed method outperforms others for Rademacher noise on real-world datasets.

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76816.9±0.616.9 \pm 0.613.8±0.313.8 \pm 0.314.6±0.314.6 \pm 0.316.6±0.516.6 \pm 0.579.9±4.279.9 \pm 4.212.9±0.312.9 \pm 0.31.7±0.7\mathbf{1.7 \pm 0.7}
Air Quality899157.9±4.157.9 \pm 4.141.6±0.741.6 \pm 0.743.1±0.743.1 \pm 0.744.0±8.344.0 \pm 8.389.7±0.189.7 \pm 0.151.7±0.551.7 \pm 0.50.7±0.3\mathbf{0.7 \pm 0.3}
Appliances1973513.0±0.213.0 \pm 0.220.0±0.520.0 \pm 0.520.8±0.520.8 \pm 0.547.3±7.747.3 \pm 7.786.1±0.286.1 \pm 0.250.5±0.550.5 \pm 0.50.5±0.2\mathbf{0.5 \pm 0.2}
Gas Drift139109.9±0.19.9 \pm 0.19.0±0.29.0 \pm 0.29.3±0.29.3 \pm 0.212.8±2.212.8 \pm 2.276.6±0.576.6 \pm 0.513.4±0.213.4 \pm 0.20.3±0.2\mathbf{0.3 \pm 0.2}
MHEALTH1000013.1±0.213.1 \pm 0.29.5±0.29.5 \pm 0.29.6±0.29.6 \pm 0.212.2±0.912.2 \pm 0.963.2±0.163.2 \pm 0.178.3±0.378.3 \pm 0.30.4±0.1\mathbf{0.4 \pm 0.1}
Power Plant956830.1±0.130.1 \pm 0.121.8±0.321.8 \pm 0.322.2±0.322.2 \pm 0.326.5±5.026.5 \pm 5.087.7±0.687.7 \pm 0.671.0±0.471.0 \pm 0.40.4±0.2\mathbf{0.4 \pm 0.2}
Household2000018.2±0.218.2 \pm 0.213.2±0.313.2 \pm 0.313.8±0.413.8 \pm 0.450.6±25.950.6 \pm 25.975.7±0.675.7 \pm 0.685.0±1.685.0 \pm 1.60.3±0.1\mathbf{0.3 \pm 0.1}

Table R14: Our proposed method outperforms others for Laplace noise on real-world datasets.

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76816.9±0.916.9 \pm 0.913.8±0.513.8 \pm 0.512.9±0.512.9 \pm 0.511.5±1.611.5 \pm 1.679.2±3.979.2 \pm 3.912.7±0.612.7 \pm 0.61.6±0.8\mathbf{1.6 \pm 0.8}
Air Quality899157.9±4.257.9 \pm 4.241.8±0.841.8 \pm 0.839.9±0.939.9 \pm 0.927.5±5.927.5 \pm 5.989.7±0.189.7 \pm 0.151.7±0.551.7 \pm 0.50.6±0.2\mathbf{0.6 \pm 0.2}
Appliances1973513.1±0.313.1 \pm 0.320.1±0.520.1 \pm 0.520.0±0.520.0 \pm 0.522.9±7.022.9 \pm 7.086.1±0.286.1 \pm 0.250.6±0.550.6 \pm 0.50.5±0.2\mathbf{0.5 \pm 0.2}
Gas Drift139109.9±0.29.9 \pm 0.29.0±0.29.0 \pm 0.29.0±0.29.0 \pm 0.28.4±0.78.4 \pm 0.776.6±0.576.6 \pm 0.513.4±0.213.4 \pm 0.20.3±0.2\mathbf{0.3 \pm 0.2}
MHEALTH1000013.1±0.213.1 \pm 0.29.5±0.29.5 \pm 0.29.2±0.29.2 \pm 0.26.9±0.36.9 \pm 0.363.2±0.263.2 \pm 0.278.2±0.378.2 \pm 0.30.3±0.1\mathbf{0.3 \pm 0.1}
Power Plant956830.2±0.330.2 \pm 0.321.7±0.421.7 \pm 0.421.3±0.421.3 \pm 0.416.9±5.516.9 \pm 5.587.6±0.787.6 \pm 0.771.2±0.671.2 \pm 0.60.5±0.2\mathbf{0.5 \pm 0.2}
Household2000018.1±0.318.1 \pm 0.313.2±0.413.2 \pm 0.413.3±0.413.3 \pm 0.426.6±24.626.6 \pm 24.675.8±0.675.8 \pm 0.685.0±1.585.0 \pm 1.50.3±0.1\mathbf{0.3 \pm 0.1}

Table R15: Our proposed method outperforms others for Student-t5t_5 noise on real-world datasets.

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76817.0±0.717.0 \pm 0.713.7±0.513.7 \pm 0.512.8±0.412.8 \pm 0.411.8±0.711.8 \pm 0.781.3±4.481.3 \pm 4.412.6±0.412.6 \pm 0.41.7±0.6\mathbf{1.7 \pm 0.6}
Air Quality899156.2±3.756.2 \pm 3.741.1±1.341.1 \pm 1.339.4±1.339.4 \pm 1.328.4±9.228.4 \pm 9.289.8±0.189.8 \pm 0.151.6±0.751.6 \pm 0.70.7±0.2\mathbf{0.7 \pm 0.2}
Appliances1973513.2±0.313.2 \pm 0.319.9±0.619.9 \pm 0.619.9±0.619.9 \pm 0.625.9±8.425.9 \pm 8.486.1±0.186.1 \pm 0.150.6±0.450.6 \pm 0.40.5±0.2\mathbf{0.5 \pm 0.2}
Gas Drift139109.9±0.29.9 \pm 0.29.0±0.29.0 \pm 0.29.0±0.29.0 \pm 0.29.6±2.09.6 \pm 2.076.4±0.576.4 \pm 0.513.4±0.313.4 \pm 0.30.3±0.1\mathbf{0.3 \pm 0.1}
MHEALTH1000013.2±0.213.2 \pm 0.29.6±0.29.6 \pm 0.29.3±0.29.3 \pm 0.27.5±0.57.5 \pm 0.563.2±0.263.2 \pm 0.278.3±0.378.3 \pm 0.30.3±0.1\mathbf{0.3 \pm 0.1}
Power Plant956830.1±0.330.1 \pm 0.321.8±0.521.8 \pm 0.521.4±0.521.4 \pm 0.517.1±11.217.1 \pm 11.287.7±0.687.7 \pm 0.670.9±0.670.9 \pm 0.60.5±0.2\mathbf{0.5 \pm 0.2}
Household2000018.1±0.318.1 \pm 0.313.2±0.413.2 \pm 0.413.3±0.413.3 \pm 0.430.3±24.630.3 \pm 24.675.7±0.775.7 \pm 0.784.8±1.584.8 \pm 1.50.3±0.2\mathbf{0.3 \pm 0.2}
AuthorsOpenReview ↗

Rebuttal 4/n

Table R16: Our proposed method outperforms others under outliers on real-world datasets.

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76888.6±1.388.6 \pm 1.384.0±5.084.0 \pm 5.081.4±6.381.4 \pm 6.334.4±17.934.4 \pm 17.972.8±3.172.8 \pm 3.115.3±3.415.3 \pm 3.47.2±3.9\mathbf{7.2 \pm 3.9}
Air Quality899181.6±0.481.6 \pm 0.482.3±1.282.3 \pm 1.282.2±1.282.2 \pm 1.252.3±21.552.3 \pm 21.589.1±0.689.1 \pm 0.650.6±4.250.6 \pm 4.22.4±1.0\mathbf{2.4 \pm 1.0}
Appliances1973564.2±11.964.2 \pm 11.943.2±3.743.2 \pm 3.742.6±3.742.6 \pm 3.752.5±26.052.5 \pm 26.085.5±2.185.5 \pm 2.149.9±4.849.9 \pm 4.81.7±0.8\mathbf{1.7 \pm 0.8}
Gas Drift1391043.1±14.243.1 \pm 14.235.8±0.635.8 \pm 0.635.9±0.635.9 \pm 0.641.2±17.441.2 \pm 17.478.2±6.978.2 \pm 6.913.6±1.113.6 \pm 1.11.5±0.6\mathbf{1.5 \pm 0.6}
MHEALTH1000041.7±0.541.7 \pm 0.533.4±0.433.4 \pm 0.432.5±0.432.5 \pm 0.412.5±4.012.5 \pm 4.061.6±9.761.6 \pm 9.776.2±13.076.2 \pm 13.01.3±0.5\mathbf{1.3 \pm 0.5}
Power Plant956854.4±5.354.4 \pm 5.346.7±1.546.7 \pm 1.546.1±1.446.1 \pm 1.437.9±18.737.9 \pm 18.786.2±6.486.2 \pm 6.470.9±3.270.9 \pm 3.21.8±0.7\mathbf{1.8 \pm 0.7}
Household2000062.1±0.362.1 \pm 0.361.4±0.561.4 \pm 0.561.6±0.561.6 \pm 0.572.1±6.272.1 \pm 6.276.0±1.676.0 \pm 1.684.6±1.984.6 \pm 1.91.0±0.3\mathbf{1.0 \pm 0.3}

Table R17: Our proposed method outperforms others when the data are not perfectly low rank (real-world datasets).

DatasetnnOLSStd PCARPCAGoDecHeteroPCADeflated-HeteroPCAGenEVD (Ours)
Energy76817.0±0.717.0 \pm 0.713.7±0.413.7 \pm 0.413.5±0.413.5 \pm 0.413.6±0.813.6 \pm 0.880.3±3.080.3 \pm 3.012.6±0.512.6 \pm 0.51.9±0.7\mathbf{1.9 \pm 0.7}
Air Quality899156.8±4.056.8 \pm 4.041.8±0.941.8 \pm 0.941.0±0.841.0 \pm 0.833.1±6.133.1 \pm 6.189.7±0.289.7 \pm 0.251.8±0.751.8 \pm 0.70.9±0.3\mathbf{0.9 \pm 0.3}
Appliances1973513.3±0.313.3 \pm 0.320.1±0.620.1 \pm 0.620.3±0.520.3 \pm 0.532.2±8.832.2 \pm 8.886.2±0.286.2 \pm 0.250.7±0.450.7 \pm 0.45.2±0.1\mathbf{5.2 \pm 0.1}
Gas Drift139109.9±0.19.9 \pm 0.19.0±0.29.0 \pm 0.29.2±0.29.2 \pm 0.211.9±2.111.9 \pm 2.176.8±0.776.8 \pm 0.713.3±0.213.3 \pm 0.21.8±0.2\mathbf{1.8 \pm 0.2}
MHEALTH1000013.4±0.213.4 \pm 0.29.6±0.29.6 \pm 0.29.5±0.29.5 \pm 0.29.0±0.59.0 \pm 0.563.2±0.263.2 \pm 0.278.5±0.478.5 \pm 0.40.7±0.2\mathbf{0.7 \pm 0.2}
Power Plant956830.3±0.330.3 \pm 0.321.9±0.421.9 \pm 0.421.8±0.421.8 \pm 0.424.3±9.524.3 \pm 9.587.8±0.587.8 \pm 0.570.8±0.670.8 \pm 0.61.0±0.3\mathbf{1.0 \pm 0.3}
Household2000018.2±0.218.2 \pm 0.213.3±0.413.3 \pm 0.413.6±0.413.6 \pm 0.450.4±20.950.4 \pm 20.975.8±0.775.8 \pm 0.785.1±1.785.1 \pm 1.70.4±0.2\mathbf{0.4 \pm 0.2}

Inference on the real-world datasets.

  • Non-Gaussian noise distributions (Tables R12–R15): we make the similar observation of GenEVD performing better than the other methods on every dataset.

  • Outliers with p=0.1p=0.1 (Table R16): GenEVD again compares favorably on every dataset.

  • Approximately low-rank signal covariance with ξ=0.01,σC2\xi=0.01\\,\sigma_{\mathcal{C}}^2 (Table R17): the same holds on every dataset.

We use semi-synthetic data because raw data do not provide the true constraints and noise covariance, which are needed to measure recovery. We can include these new experiments in the main manuscript.


Minor: GenEVD has not been defined before Lemma 1, which already references it. Can you reorganize the flow or reword Lemma 1 to make this clearer?

A: We thank the reviewer for this suggestion. We will define GenEVD before Lemma 1: given a noise-covariance estimate Σ^ϵ⪰0\widehat{\mathbf{\Sigma}}_{\epsilon}\succeq0, GenEVD estimates row(A)\mathrm{row}(\mathbf{A}) by the span of the mm generalized eigenvectors of (Sy,Σ^ϵ)(\mathbf{S}_y,\widehat{\mathbf{\Sigma}}_{\epsilon}) whose finite eigenvalues are closest to one, computed by the QZ algorithm, and Algorithm 1 alternates this step with an update of Σ^ϵ\widehat{\mathbf{\Sigma}}_{\epsilon}.

Reviewer_tMQ1OpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
1
Soundness
3
Read review
Paper summary

The authors consider the setting where data vectors are observed that are noisy versions of the solutions to a set of linear equations. The goal is to estimate both the linear equations (more precisely the row space of the matrix of linear equalities) and the covariance matrix of the error. The method allows the error covariance matrix to be fairly general and even singular (although with a prespecified support) and even estimates the number of linearly independent constraints. They provide identifiability conditions, an estimation procedure, finite-sample bounds, and establish minimax-rate-optimality of their approach. Their validation includes semi-synthetic experiments in which they start with actual data sets but then transform them into the structure studied in the paper.

Critical strengths

The problem is a fundamental one and the authors provide a fairly general solution. The treatment is pretty thorough: for example, there is a minimax lower bound, which establishes rate optimality of the method.

Critical weaknesses

I did not find this paper's writing conducive to human understanding. One problem is that it doesn't read linearly as a paper should. An example: the line "Ordinary least squares (OLS) minimizes squared response residuals when the regressors are treated as exact" comes without any previous reference to "the regressors" in the paper or what those may be referring to. Another example: kappa_Phi is defined in (1) with no discussion of what it represents or why it needs to be defined. It's only two pages later, just after (5), that it is first referenced in the text. There are also odd choices about what to explain and what to leave unexplained. The notation section introduces very familiar notation like Euclidean, spectral and Frobenius norm, but then Assumption 1 uses the notation ∥⋅∥ψ2\|\cdot\|_{\psi_2} without definition, assuming the reader will infer that this is the Orlicz norm. In general, the paper feels like a sequence of technical statements rather than something that is trying to provide understanding and build a reader's intuition.

Questions for authors

None

4 comments
AuthorsOpenReview ↗

Rebuttal 1/n

We thank the reviewer for the careful reading and for the specific suggestions on presentation. We have added more context at the specific locations flagged by the reviewer. We kindly request the reviewer to let us know if they have any further questions, and we hope that these revisions address the reviewer's concerns.

We also conducted new experiments during the author-reviewer discussion phase, as requested by Reviewers 6waE and 7AQR. We summarize them as follows; the details are in our responses to those reviewers.

  • Initialization (Tables R1–R3). From six starts, including random ones, GenEVD reached the same estimate in every run.

  • Number of relations (Table R4). Compared with thresholding the spectrum of Sy\mathbf{S}_y, our method never returned a wrong mm, including Example A, where thresholding was wrong in every trial.

  • OLS given the noise-free variables (Table R5). GenEVD coincides with OLS when only the response is noisy, and recovers the coefficients when a predictor is also noisy, where OLS is biased.

  • Larger dimensions (Table R6). At d=50d=50 and d=100d=100, GenEVD performs better than the other methods.

  • Non-Gaussian noise (Table R9). The accuracy of GenEVD is unchanged, and it compares favorably with the other methods, including for heavy-tailed Student-t5t_5 noise.

  • Outliers (Table R10). GenEVD also performs better than the other methods under outliers on top of dense noise.

  • Data that are not perfectly low rank (Table R11). We see the same trend when the relations hold up to a small residual variance.


The authors consider the setting where data vectors are observed that are noisy versions of the solutions to a set of linear equations. The goal is to estimate both the linear equations (more precisely the row space of the matrix of linear equalities) and the covariance matrix of the error. The method allows the error covariance matrix to be fairly general and even singular (although with a prespecified support) and even estimates the number of linearly independent constraints. They provide identifiability conditions, an estimation procedure, finite-sample bounds, and establish minimax-rate-optimality of their approach. Their validation includes semi-synthetic experiments ... the paper.

A: We thank the reviewer for the summary. In continuation, structural restrictions on Σϵ\mathbf{\Sigma}_{\epsilon}, such as a support, are necessary in the general model. In our tests, a withheld zero variance was recovered and the tested misspecified support was detected. Tables R7 and R8 repeat the relevant entries of Tables 8–11, which are already presented in the paper (Appendix L).

  • A withheld zero variance is recovered (Table R7). Setup: Case Study 1 with diag(Σϵ)=(0.10,0.26,0.375,0.425,0)\mathrm{diag}(\mathbf{\Sigma}_{\epsilon})=(0.10,0.26,0.375,0.425,0), m=3m=3; the zero variance of variable 5 is withheld, so all five diagonal entries are unknowns.

Table R7: Our proposed method recovers a withheld zero noise variance.

Method (number of relations kk)λ^(k)\widehat\lambda_{(k)}[Σ^ϵ]55[\widehat{\mathbf{\Sigma}}_{\epsilon}]_{55} (true 00)∥Σ^ϵ−Σϵ∥F\Vert \widehat{\mathbf{\Sigma}}_{\epsilon}-\mathbf{\Sigma}_{\epsilon}\Vert _F
GenEVD, k=3k=3 (true mm)0.982±0.0250.982\pm0.0250.001±0.0020.001\pm0.0020.019±0.0070.019\pm0.007
GenEVD, k=4k=42.434±0.0062.434\pm0.0060.868±0.0180.868\pm0.0181.650±0.0381.650\pm0.038
HeteroPCA, k=3k=3--0.788±0.2790.788\pm0.2795.533±1.9605.533\pm1.960
Deflated-HeteroPCA, k=3k=3--0.870±0.0180.870\pm0.0183.838±0.1043.838\pm0.104
  • GenEVD recovers the withheld zero variance and keeps its unity eigenvalue. The fit with k=4k=4 and both HeteroPCA variants absorb signal into [Σ^ϵ]55[\widehat{\mathbf{\Sigma}}_{\epsilon}]_{55}, and the k=4k=4 fit fails the unity test.

  • The tested misspecified support is detected by non-unity eigenvalues (Table R8). Setup: Case Study 1 with s=1s=1, m=3m=3; the true pair (1,3)(1,3) is replaced by (1,2)(1,2), so the number of unknowns (q=5q=5) is unchanged.

Table R8: Non-unity eigenvalues detect the tested misspecified support.

nnCorrect support, λ^(3)\widehat\lambda_{(3)}Wrong support, λ^(3)\widehat\lambda_{(3)}Wrong support, $\vert \widehat\lambda_{(3)}-1\vert $
5001.007±0.0941.007\pm0.0940.912±0.3240.912\pm0.3240.331±0.0470.331\pm0.047
10000.998±0.0640.998\pm0.0640.899±0.3030.899\pm0.3030.317±0.0310.317\pm0.031
20001.005±0.0511.005\pm0.0510.867±0.2880.867\pm0.2880.315±0.0220.315\pm0.022
50001.005±0.0311.005\pm0.0310.871±0.2870.871\pm0.2870.313±0.0140.313\pm0.014
  • With the wrong support, ∣λ^(3)−1∣|\widehat\lambda_{(3)}-1| stays near 0.310.31 as nn grows and exceeds τ=0.1\tau=0.1 of Algorithm 2, so the fit is rejected. With the correct support, λ^(3)\widehat\lambda_{(3)} concentrates at one.

  • The baselines do not use the support, so they return the same estimate under both supports and cannot flag the error.

  • Semi-synthetic design. It lets us measure recovery, since raw data do not provide the true constraints and noise covariance.

AuthorsOpenReview ↗

Rebuttal 2/n


The problem is a fundamental one and the authors provide a fairly general solution. The treatment is pretty thorough: for example, there is a minimax lower bound, which establishes rate optimality of the method.

A: We sincerely thank the reviewer for these kind words. In continuation, the paper adds the following to prior work.

  • The constraints are the generalized eigenvectors of (Σy,Σϵ)(\mathbf{\Sigma}_y,\mathbf{\Sigma}_{\epsilon}) with eigenvalue one. This needs no inverse of Σϵ\mathbf{\Sigma}_{\epsilon}, so it works with noise-free variables, and it recovers IPCA (Lemma 1) and OLS (Theorem 2) as special cases.

  • The exact identifiability condition and an error bound for a correlated, possibly singular Σϵ\mathbf{\Sigma}_{\epsilon} (Theorems 4 and 5).

  • A finite-sample guarantee for the alternating algorithm itself (Theorem 8).

  • A guarantee for estimating the number of relations (Theorem 6).


Improving the presentation

I did not find this paper’s writing conducive to human understanding. One problem is that it doesn’t read linearly as a paper should. An example: the line “Ordinary least squares (OLS) minimizes squared response residuals when the regressors are treated as exact” comes without any previous reference to “the regressors” in the paper or what those may be referring to. Another example: kappa_Phi is defined in (1) with no discussion of what it represents or why it needs to be defined. It’s only two pages later, just after (5), that it is first referenced in the text. There are also odd choices about what to explain and what to leave unexplained. The notation section introduces very familiar notation like Euclidean, spectral and Frobenius norm, but then Assumption 1 uses the notation ∣⋅∣ψ2|\cdot|_{\psi_2} without definition, assuming the reader will infer that this is the Orlicz norm. In general, the paper feels like a sequence of technical statements rather than something that is trying to provide understanding and build a reader’s intuition.

A: We sincerely thank the reviewer for these concrete examples, and we agree with them. We have revised the paper as follows.

  1. Regressors (Section 2, before Theorem 2). We added: “Ordinary least squares (OLS) corresponds to one relation in which all variables but one are noise-free. Partition y=(z,r)\mathbf y=(\mathbf z,r), where the regressors z∈Rd−1\mathbf z\in\mathbb R^{d-1} are noise-free and the response rr is the only noisy variable, so that Σϵ=c,ededT\mathbf{\Sigma}_{\epsilon}=c\\,\mathbf e_d\mathbf e_d^{\mathsf{T}} for some c>0c > 0 and the latent signal satisfies xd=βT(x1,…,xd−1)Tx_d=\boldsymbol{\beta}^{\mathsf{T}}(x_1,\ldots,x_{d-1})^{\mathsf{T}}. OLS estimates β\boldsymbol{\beta} by the least-squares regression of rr on z\mathbf z.”

  2. κΦ\kappa_\Phi (right after Eq. (1)). We added: “Given A\mathbf{A}, the moment equation ΦA,S(θ)=AΣyAT\Phi_{\mathbf{A},\mathcal{S}}(\boldsymbol{\theta})=\mathbf{A}\mathbf{\Sigma}_y\mathbf{A}^{\mathsf{T}} is a linear system for the qq noise parameters, and κΦ\kappa_\Phi is the largest factor by which an error in its right-hand side is amplified in the least-squares solution for θ\boldsymbol{\theta}. It thus plays for Σϵ\mathbf{\Sigma}_{\epsilon} the role that 1/σC21/\sigma_{\mathcal{C}}^2 plays for C\mathcal{C} (Theorem 3), and κΦ=∞\kappa_\Phi=\infty when the unrestricted supported moment map is noninjective.”

  3. The ψ2\psi_2 norm. We defined ∥Z∥ψ2:=inf⁡t>0:Eexp⁡(Z2/t2)≤2\Vert Z\Vert _{\psi_2}:=\inf\\{t > 0:\mathbb E\exp(Z^2/t^2)\le2\\} (Vershynin, 2018, Ch. 2) in the notation paragraph and moved the standard norms to Appendix A.

AuthorsOpenReview ↗

Rebuttal 3/n

Building Intuition

We added the following intuition in Section 2, just before the Identifiability paragraph, and each subsection of Section 3 now opens with the question it answers.

  • Generalized eigenvalue formulation. Since y=x+ϵ\mathbf y=\mathbf x+\boldsymbol{\epsilon} and Ax=0\mathbf{A}\mathbf x=\mathbf 0, we have Ay=Aϵ\mathbf{A}\mathbf y=\mathbf{A}\boldsymbol{\epsilon}. As x\mathbf x and ϵ\boldsymbol{\epsilon} are zero mean and uncorrelated,

ΣyAT=E[y(Ay)T]=E[(x+ϵ)(Aϵ)T]=ΣϵAT.\mathbf{\Sigma}_y\mathbf{A}^{\mathsf{T}}=\mathbb E\left[\mathbf y(\mathbf{A}\mathbf y)^{\mathsf{T}}\right]=\mathbb E\left[(\mathbf x+\boldsymbol{\epsilon})(\mathbf{A}\boldsymbol{\epsilon})^{\mathsf{T}}\right]=\mathbf{\Sigma}_{\epsilon}\mathbf{A}^{\mathsf{T}}.

Hence every vector in row(A)\mathrm{row}(\mathbf{A}) is a generalized eigenvector of Σyv=λΣϵv\mathbf{\Sigma}_y\mathbf v=\lambda\mathbf{\Sigma}_{\epsilon}\mathbf v with λ=1\lambda=1, and the other generalized eigenvalues are larger than one or infinite.

  • Challenges 1 and 2 (heterogeneity, non-diagonal Σϵ\mathbf{\Sigma}_{\epsilon}). Any Σϵ≻0\mathbf{\Sigma}_{\epsilon}\succ0 can be handled through its inverse: with the Cholesky factor Σϵ=LLT\mathbf{\Sigma}_{\epsilon}=\mathbf L\mathbf L^{\mathsf{T}}, the problem is equivalent to the scaled eigenvalue problem L−1ΣyL−Tw=λw\mathbf L^{-1}\mathbf{\Sigma}_y\mathbf L^{-\mathsf{T}}\mathbf w=\lambda\mathbf w with w=LTv\mathbf w=\mathbf L^{\mathsf{T}}\mathbf v, which is the step of IPCA (Lemma 1).

  • Challenge 3 (singularity). When Σϵ\mathbf{\Sigma}_{\epsilon} is singular, L−1\mathbf L^{-1} does not exist and IPCA is undefined. We therefore solve Σyv=λΣϵv\mathbf{\Sigma}_y\mathbf v=\lambda\mathbf{\Sigma}_{\epsilon}\mathbf v directly with the QZ algorithm, which needs no inverse; each noise-free direction (Σϵv=0\mathbf{\Sigma}_{\epsilon}\mathbf v=\mathbf 0) gives an infinite generalized eigenvalue. For example, when only the response is noisy, Σϵ\mathbf{\Sigma}_{\epsilon} is singular and GenEVD recovers OLS (Theorem 2).

  • Challenge 4 (unknown mm and Σϵ\mathbf{\Sigma}_{\epsilon}). We first analyze two simpler problems.

    • Known Σϵ\mathbf{\Sigma}_{\epsilon} and mm: C=Null(Σy−Σϵ)\mathcal{C}=\mathrm{Null}(\mathbf{\Sigma}_y-\mathbf{\Sigma}_{\epsilon}), and replacing Σy\mathbf{\Sigma}_y by Sy\mathbf{S}_y gives an error of O((d+log⁡(1/δ))/n)O(\sqrt{(d+\log(1/\delta))/n)} (Theorem 3).
    • Known A\mathbf{A} and support S\mathcal{S}: the moment equation AΣyAT=AΣϵAT\mathbf{A}\mathbf{\Sigma}_y\mathbf{A}^{\mathsf{T}}=\mathbf{A}\mathbf{\Sigma}_{\epsilon}\mathbf{A}^{\mathsf{T}} is linear in the qq free parameters of Σϵ\mathbf{\Sigma}_{\epsilon}, which are uniquely determined exactly when the moment map ΦA,S\Phi_{\mathbf{A},\mathcal{S}} has full column rank; this requires q≤m(m+1)/2q\le m(m+1)/2 (Theorems 4 and 5).
    • Algorithm 1 alternates the two steps (Theorem 8), and Algorithm 2 estimates mm by counting the unity eigenvalues (Theorem 6).
AuthorsOpenReview ↗

A gentle reminder

Dear Reviewer tMQ1,

Thank you again for your feedback. We revised the manuscript to address the presentation issues you flagged and added a short derivation to build intuition for the generalized eigenvalue step. As the author-reviewer discussion deadline is approaching fast, we would greatly appreciate hearing whether any points still need clarification.

Best regards,

Authors

Reviewer_6waEOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper presents an approach to recover linear constraints on a system in the presence of unknown, correlated and singular measurement noise. It provides methods to estimate both the constraint subspace and the noise covariance matrix; it also provides a method to estimate the number of constraints.

Critical strengths

The problem is worth studying, particularly for systems where some measurements are exact. The identifiability analysis is helpful, and shows that subspace errors enter the covariance update quadratically. This explains the local convergence results well. The paper also develops a minimax lower bound and shows that the established error rate matches with nn and dd.

Critical weaknesses

The proof requires that the initial guess be close to the true noise covariance, but it is unclear when the diagonal initialization used in the experiments would meet this requirement. Experiments with different initial guesses would provide insight into how much this matters in practice.

Under Assumption 4, it appears that directly thresholding the sample-covariance eigenvalues would already allow for estimation of the number of constraints. What does the proposed descending search add under the same assumption?

Questions for authors

It is also helpful to have more experimental comparisons. GenEVD is provided with the noise support and the noise-free coordinates, whereas OLS selects its own predictors. In the semi-synthetic experiments, I would like to see OLS use those same noise-free coordinates.

The experiments scale are relatively small, with five variables in most cases and ten in the synthetic example.

5 comments
AuthorsOpenReview ↗

Rebuttal 1/n

We thank the reviewer for the careful reading and the positive evaluation. We have conducted new experiments on initialization, order selection, comparison with OLS given noise-free variables, and larger dimensions, as requested by the reviewer. We have also provided clarifications for other questions. We kindly request the reviewer to let us know if they have any further questions.

Other new experiments in this rebuttal. Details are in our response to Reviewer 7AQR.

  • Non-Gaussian noise (Tables R9 and R12–R15). We observe that GenEVD performs better than the other methods on synthetic and real-world datasets for uniform, Rademacher, Laplace and Student-t5t_5 noise.

  • Outliers (Tables R10 and R16). GenEVD again performs better than the other methods on synthetic and real-world datasets.

  • Data that are not perfectly low rank (Tables R11 and R17). GenEVD also compares favorably with the other methods on synthetic and real-world datasets when the relations hold up to a small residual variance.


The paper presents an approach to recover linear constraints on a system in the presence of unknown, correlated and singular measurement noise. It provides methods to estimate both the constraint subspace and the noise covariance matrix; it also provides a method to estimate the number of constraints

A: We thank the reviewer for the summary. In continuation, singularity is what makes the problem challenging. When some variables are exact, Σϵ\mathbf{\Sigma}_{\epsilon} has no inverse, so the inverse-Cholesky step of IPCA (Narasimhan & Shah, 2008) is undefined. Our algorithm, GenEVD, needs no inverse. Since Σyv=Σϵv  ⟺  Σxv=0\mathbf{\Sigma}_y\mathbf v=\mathbf{\Sigma}_{\epsilon}\mathbf v\iff\mathbf{\Sigma}_x\mathbf v=\mathbf 0, the constraints are the generalized eigenvectors with eigenvalue one. This is what allows the rowspace, Σϵ\mathbf{\Sigma}_{\epsilon} and mm to be estimated with guarantees (Theorems 3, 5, 6 and 8).


The problem is worth studying, particularly for systems where some measurements are exact.

A: We appreciate the reviewer’s recognition of this motivation. Exact measurements make the noise covariance singular even when the observed-data covariance is positive definite. We show that our method, GenEVD recovers the iterative PCA (Narasimhan & Shah, 2008) solution (Lemma 1) and OLS solution (Theorem 2) in the respective settings.


The identifiability analysis is helpful, and shows that subspace errors enter the covariance update quadratically. This explains the local convergence results well. The paper also develops a minimax bound and shows that the established error rate matches with nn and dd.

A: We sincerely thank the reviewer for these positive remarks. We add that, in the general model, structural restrictions on Σϵ\mathbf{\Sigma}_{\epsilon}, such as a support, are necessary, not only for our method.

  • Theorem 4 gives the exact condition under which a given support is identifiable.

  • The reason is a count of degrees of freedom. The covariance Σy=Σx+Σϵ\mathbf{\Sigma}_y=\mathbf{\Sigma}_x+\mathbf{\Sigma}_{\epsilon} has d(d+1)/2d(d+1)/2 distinct entries. But if dd variables of xx satisfy mm linear relations, then Σx\mathbf{\Sigma}_x has rank d−md-m, and such matrices have d(d+1)/2−m(m+1)/2d(d+1)/2-m(m+1)/2 degrees of freedom. Hence at most m(m+1)/2m(m+1)/2 equations remain for the unknown entries of Σϵ\mathbf{\Sigma}_{\epsilon}.

AuthorsOpenReview ↗

Rebuttal 2/n

Experiments with different initializations converge to good estimates for our proposed method

The proof requires that the initial guess be close to the true noise covariance, but it is unclear when the diagonal initialization used in the experiments would meet this requirement. Experiments with different initial guesses would provide insight into how much this matters in practice.

A: We thank the reviewer for this important question. We ran the experiment and observed that our proposed method performs well for various different initializations. The experimental setup and results are presented below.

  • Setup. We use Case Study 1 with s∈0,1,2s\in\\{0,1,2\\} exact coordinates (n=5000n=5000, 50 trials) and Case Study 2 (n=20000n=20000, 30 trials). We tried GenEVD for six initial noise covariances Σϵ(1)\mathbf{\Sigma}_{\epsilon}^{(1)}:

    • the scaled diagonal c,diag(Sy)c\\,\mathrm{diag}(\mathbf{S}_y) with exact entries set to zero, for c∈10−4,0.01,0.1,0.5c\in\\{10^{-4},0.01,0.1,0.5\\} (the paper uses c=0.5c=0.5).

    • a diagonal matrix with random entries.

    • a non-diagonal matrix with random entries.

  • Metrics (lower value is better for all three).

    • Constraint subspace (Table R1): θmax⁡=(180/π)arcsin⁡(min⁡1,∥P^−P⋆∥op)\theta_{\max}=(180/\pi)\arcsin(\min\\{1,\Vert \widehat{P}-P_\star\Vert _{\mathrm{op}}\\}), where P^\widehat{P} and P⋆P_\star are the orthogonal projectors onto the estimated and the true constraint subspaces, as in Appendix M.2. We report it for the first iterate A(1)\mathbf{A}^{(1)} and for the final estimate.

    • Noise covariance (Table R2): ∥θ−θ⋆∥2\Vert \theta-\theta^\star\Vert _2, where θ\theta collects the qq supported entries, as in Tables 6, 7 and 13. We report it for the start θ(1)\theta^{(1)} and for the final estimate θ^\widehat{\theta}.

    • Unity eigenvalues (Table R3): max⁡j≤m∣λ^(j)−1∣\max_{j\le m}|\widehat{\lambda}_{(j)}-1|, where λ^(j)\widehat{\lambda}_{(j)} is the jjth finite generalized eigenvalue of the final pencil (Sy,Σ^ϵ)(\mathbf{S}_y,\widehat{\mathbf{\Sigma}}_{\epsilon}) after sorting by ∣λ^−1∣|\widehat{\lambda}-1|, as in Appendix L. A value of 00 means that all mm fitted constraint eigenvalues equal one.

Table R1: Different initializations converge to a good estimate of the constraint subspace.

Start Σϵ(1)\mathbf{\Sigma}_{\epsilon}^{(1)}CS1, s=0s=0, FirstCS1, s=0s=0, FinalCS1, s=1s=1, FirstCS1, s=1s=1, FinalCS1, s=2s=2, FirstCS1, s=2s=2, FinalCS2, FirstCS2, Final
10−4,diag(Sy)10^{-4}\\,\mathrm{diag}(\mathbf{S}_y)1.2±0.41.2\pm0.40.464±0.2060.464\pm0.2060.5±0.20.5\pm0.20.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.2±0.11.2\pm0.10.275±0.0750.275\pm0.075
0.01,diag(Sy)0.01\\,\mathrm{diag}(\mathbf{S}_y)1.2±0.41.2\pm0.40.464±0.2060.464\pm0.2060.5±0.20.5\pm0.20.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.2±0.11.2\pm0.10.275±0.0750.275\pm0.075
0.1,diag(Sy)0.1\\,\mathrm{diag}(\mathbf{S}_y)1.2±0.41.2\pm0.40.464±0.2060.464\pm0.2060.5±0.20.5\pm0.20.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.2±0.11.2\pm0.10.275±0.0750.275\pm0.075
0.5,diag(Sy)0.5\\,\mathrm{diag}(\mathbf{S}_y)1.2±0.41.2\pm0.40.464±0.2060.464\pm0.2060.5±0.20.5\pm0.20.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.2±0.11.2\pm0.10.275±0.0750.275\pm0.075
random diagonal1.7±0.61.7\pm0.60.464±0.2060.464\pm0.2060.9±0.40.9\pm0.40.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.6±0.31.6\pm0.30.275±0.0750.275\pm0.075
random non-diagonal1.8±0.61.8\pm0.60.464±0.2060.464\pm0.2061.0±0.41.0\pm0.40.417±0.1680.417\pm0.1680.3±0.10.3\pm0.10.284±0.1160.284\pm0.1161.7±0.31.7\pm0.30.275±0.0750.275\pm0.075

Table R2: Different initializations converge to a good estimate of the noise covariance.

Start Σϵ(1)\mathbf{\Sigma}_{\epsilon}^{(1)}CS1, s=0s=0, StartCS1, s=0s=0, FinalCS1, s=1s=1, StartCS1, s=1s=1, FinalCS1, s=2s=2, StartCS1, s=2s=2, FinalCS2, StartCS2, Final
10−4,diag(Sy)10^{-4}\\,\mathrm{diag}(\mathbf{S}_y)0.64±0.000.64\pm0.000.020±0.0080.020\pm0.0080.64±0.000.64\pm0.000.019±0.0080.019\pm0.0080.47±0.000.47\pm0.000.010±0.0050.010\pm0.0050.37±0.000.37\pm0.000.023±0.0100.023\pm0.010
0.01,diag(Sy)0.01\\,\mathrm{diag}(\mathbf{S}_y)0.56±0.000.56\pm0.000.020±0.0080.020\pm0.0080.55±0.000.55\pm0.000.019±0.0080.019\pm0.0080.41±0.000.41\pm0.000.010±0.0050.010\pm0.0050.32±0.000.32\pm0.000.023±0.0100.023\pm0.010
0.1,diag(Sy)0.1\\,\mathrm{diag}(\mathbf{S}_y)0.28±0.020.28\pm0.020.020±0.0080.020\pm0.0080.28±0.020.28\pm0.020.019±0.0080.019\pm0.0080.25±0.010.25\pm0.010.010±0.0050.010\pm0.0050.21±0.000.21\pm0.000.023±0.0100.023\pm0.010
0.5,diag(Sy)0.5\\,\mathrm{diag}(\mathbf{S}_y)3.81±0.083.81\pm0.080.020±0.0080.020\pm0.0083.79±0.093.79\pm0.090.019±0.0080.019\pm0.0083.00±0.073.00\pm0.070.010±0.0050.010\pm0.0052.31±0.022.31\pm0.020.023±0.0100.023\pm0.010
random diagonal3.36±1.293.36\pm1.290.020±0.0080.020\pm0.0083.54±1.253.54\pm1.250.019±0.0080.019\pm0.0082.57±1.172.57\pm1.170.010±0.0050.010\pm0.0052.20±0.682.20\pm0.680.023±0.0100.023\pm0.010
random non-diagonal3.27±1.413.27\pm1.410.020±0.0080.020\pm0.0083.39±1.303.39\pm1.300.019±0.0080.019\pm0.0082.79±1.282.79\pm1.280.010±0.0050.010\pm0.0052.27±0.652.27\pm0.650.023±0.0100.023\pm0.010
AuthorsOpenReview ↗

Rebuttal 3/n

Table R3: Different initializations converge to fits with mm eigenvalues close to one.

Start Σϵ(1)\mathbf{\Sigma}_{\epsilon}^{(1)}CS1, s=0s=0CS1, s=1s=1CS1, s=2s=2CS2
10−4,diag(Sy)10^{-4}\\,\mathrm{diag}(\mathbf{S}_y)(3.5±1.4)×10−15(3.5\pm1.4)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.6±0.8)×10−14(1.6\pm0.8)\times10^{-14}
0.01,diag(Sy)0.01\\,\mathrm{diag}(\mathbf{S}_y)(3.3±1.3)×10−15(3.3\pm1.3)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.4±0.7)×10−14(1.4\pm0.7)\times10^{-14}
0.1,diag(Sy)0.1\\,\mathrm{diag}(\mathbf{S}_y)(3.5±1.3)×10−15(3.5\pm1.3)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.7±1.0)×10−14(1.7\pm1.0)\times10^{-14}
0.5,diag(Sy)0.5\\,\mathrm{diag}(\mathbf{S}_y)(3.6±1.5)×10−15(3.6\pm1.5)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.5±0.7)×10−14(1.5\pm0.7)\times10^{-14}
random diagonal(3.7±1.8)×10−15(3.7\pm1.8)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.7±0.7)×10−14(1.7\pm0.7)\times10^{-14}
random non-diagonal(3.7±1.7)×10−15(3.7\pm1.7)\times10^{-15}0.020±0.0170.020\pm0.0170.033±0.0180.033\pm0.018(1.7±0.7)×10−14(1.7\pm0.7)\times10^{-14}

Inference: Hence, we observe that the estimates for all variables constraint matrix, noise-covariance, and number of linear relations converge close to true values for different initializations.


Experiments on estimation of number of linear relations

Under Assumption 4, it appears that directly thresholding the sample-covariance eigenvalues would already allow for estimation of the number of constraints. What does the proposed descending search add under the same assumption?

A: We thank the reviewer for this insightful question. Yes, thresholding the spectrum of Sy\mathbf{S}_y can recover mm under Assumption 4, but it needs a threshold that separates λm(Σy)\lambda_m(\mathbf{\Sigma}_y) and λm+1(Σy)\lambda_{m+1}(\mathbf{\Sigma}_y) (eigenvalues in increasing order), which may not be available to the practitioner. Our proposed method instead counts the unity eigenvalues.

We conduct experiments to show that choosing a wrong threshold for the spectrum of Σy\mathbf{\Sigma}_y may lead to an incorrect estimate of mm, whereas our method finds the correct mm. The setup, results, and inference are presented below.

We conduct experiments on two systems and report the mean and success rate (SR) from 100100 runs for Case Study 1 and 200200 runs for Example A:

  • Case Study 1 from the main manuscript. It has d=5d = 5, m=3m=3 and s∈0,1,2s\in\\{0,1,2\\}. We observe that both approaches estimate the correct mm in all 100100 runs, that is, a 100100\\% success rate.

  • Example A: We construct a simple setup with d=3d = 3, m=1m=1. We use x=(z1,z2,z1+z2)\mathbf x=(z_1,z_2,z_1+z_2) with independent unit-variance z1,z2z_1,z_2; variables 1-2 are noise-free, and variable 3 has noise variance 44. We use t=5t=5 for both methods; it bounds the noise (Σϵ⪯5,I\mathbf{\Sigma}_{\epsilon}\preceq5\\,\mathbf{I}) but exceeds σC2=1\sigma_{\mathcal{C}}^2=1, so Assumption 4 does not hold. Thresholding returns m^=2\widehat m=2, whereas our method estimates the correct m=1m=1. Our method also uses the support of Σϵ\mathbf{\Sigma}_{\epsilon}: with two noise-free variables, the pencil (Sy,Σ^ϵ)(\mathbf{S}_y,\widehat{\mathbf{\Sigma}}_{\epsilon}) has at most one finite eigenvalue, so k=2k=2 is rejected.

Table R4: Our proposed method recovers the number of relations.

SettingTrue mmEigenvalues of Σy\mathbf{\Sigma}_yt=σˉ2t=\bar\sigma^2Thresholding, m^\widehat mThresholding, SROurs, $\vert \widehat\lambda^{[m]}_{(m)}-1\vert $Ours, $\vert \widehat\lambda^{[m+1]}_{(m+1)}-1\vert $Ours, m^\widehat mOurs, SR
Case Study 1, s=0s=030.09, 0.23, 0.41, 2.50, 14.030.09,\ 0.23,\ 0.41,\ 2.50,\ 14.030.4731002.5×10−152.5\times10^{-15}4.694.693100
Case Study 1, s=1s=130.04, 0.21, 0.41, 2.47, 14.030.04,\ 0.21,\ 0.41,\ 2.47,\ 14.030.4731000.0190.019∞\infty3100
Case Study 1, s=2s=230.03, 0.12, 0.25, 2.47, 13.870.03,\ 0.12,\ 0.25,\ 2.47,\ 13.870.4431000.0300.030∞\infty3100
Example A10.63, 1, 6.370.63,\ 1,\ 6.375202×10−162\times10^{-16}∞\infty1100

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.