Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper proposes a method for evaluating the likelihood and for sampling from the posterior of Gaussian Markov random field $X$ given some linear constraints $X | AX = b$ where $A$ is a sparse matrix. The method is based on the SVD of $A$, which may be computed for a small cost if one can identify rows of $A$ that don't share columns with non-zero elements. 

The method is illustrated on two toy examples, where it is shown that it provides massive computational gains. It is however unclear if the competitors considered in the benchmark are the actual alternatives a practitioner would consider.

-----------------------
The author's rebuttal makes me confident that the shortcomings I've identified have been understood by the authors and that they are in a good position to address them at the camera ready stage. I'm thus upgrading my score from 5 to 6.
main_review: **Writing**

I found the paper to be globally well written and the exposition easy to follow. One shortcoming in my view is that the method could be better motivated (I had to look at the references to convince myself that the problem tackled by the paper had a practical significance). In its current form the paper only specifies that "hard constraints have a cost that scales cubically with the number of constraints" but since this is the core issue that is addressed in this work a little hand holding would be appreciated. In my opinion providing more explanations about why the issue arises and a better positioning of the paper with respect to the prior work (ie how this is currently dealt with) would significantly improve the paper quality.

**Methodology**

The proposed methodology is sound but there is a chance that the assumptions that are added on the sparsity patterns of $A$ when introducing the method could be used in the first place to cut down the complexity of the sampling and of the likelihood evaluation. I believe this could for example be done with the sparse inverse subset method as described in [1].

**Significance**

The feeling that this contribution is of interest to the community would be much stronger if the authors were to give a better description of how the problem they address is currently tackled (or unsolved) and what are the shortcomings. At the moment it seems that they mainly compare a naive baseline which results in impressive results but does not seem to be a fair comparison. For example, my understanding is that using observations as nodes for the triangulation would be a perfectly valid way to tackle the problem in Experiment 6.1.

**Experiments**

Three remarks:
 - Since the proposed method loses its interest when $A$ cannot be split into "independent rows", it would be interesting to increase the number of constraints up to the point where this becomes the case.
 - Could an explanation of why the evaluation time decreases with the number of constraints be included in the result analysis?
 - Is the computation of $T$ included in the timings that are reported?


[1] Durrande, Nicolas, et al. "Banded matrix operators for Gaussian Markov models in the automatic differentiation era." The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2019.

limitations_and_societal_impact: No specific comments
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a basis transformation method to speed up inference in Gauss--Markov random fields under certain sparse constraints. 


main_review: 
- Typo? (Line 74) 

I believe the first minus sign should be a plus in the conditional mean expression. 

- sum-to-zero constraints a violation of assumptions? (Line 191)

It would seem like a sum-to-zero constraint would violate the assumptions on the constraint matrix from Sec 3.1?

- y-axis in Fig 1. 

It might be preferable to use a logarithmic scaling of the y-axis for readability.

- Computational time decreasing with number of observations (Line 269)

This would require further explanation.

   
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper formulates a class of computationally efficient methods for Gaussian Markov Random field (GMRF) models with linear constraints. The main idea behind the methods relies on a transformation of basis such that the constraints are easier to enforce upon transformation. The methods outperform existing alternative formulations of GMRFs under scenarios involving large numbers of sparse constraints. Finally, a GMRF for linearly constrained Gaussian process regression is derived by utilizing the proposed methods in conjunction with the stochastic partial differential equation (SPDE) approach.

main_review: Originality: The efficient GMRF methods introduced in this work perform transformation of basis that separates constrained and unconstrained subspaces using SVD, thereby bypassing sparsity challenges and allowing for effective enforcement of the constraints in the transformed space. Nevertheless, the idea of precision matrix decomposition through SVD, or many other decomposition methods for that matter has been extensively studied. In that sense, this work appears to be a combination of well-known practices with sparse gaussian random field models. In other words, the main originality lies in using matrix decomposition in a linearly constrained GMRF setting, however, the idea of precision matrix decomposition in general is well-studied. Also, related studies involving efficient GMRFs based on SVD/eigenvalue/Cholesky decomposition do not seem to be given credit.

Quality: The proposed GMRF methods are (1) introduced primarily for GMRFs with sparse hard (linear) constraints, (2) extended to cases of both hard and soft constraints, and (3) derived and adapted for constrained Gaussian processes. Each variant is technically sound and well supported by theoretical claims involving reasonable assumptions on the positive semi-definiteness of the precision matrix Q (typically assumed in similar settings) and likelihood derivations. Also, using the change of basis, alternative formulations of the distributions of AX and X|AX = b are derived, suitable for efficient sampling and likelihood calculation.

Clarity: The paper is generally well written and organized. The notation is clear, not difficult to follow, and consistent throughout the paper.

Significance: The problem considered in this paper is of considerable importance as efficient sampling and inference with GMRFs as well as constrained Gaussian processes find application in a broad range of areas. On the other hand, I believe that the narrow (i.e., quite specific) settings of the experimental design (particularly in the data generation process) limit the contribution’s significance.

UPDATE AFTER THE REBUTTAL: In their response, the authors have addressed the majority of the comments that I have raised. The authors have also conducted the additional assessment of the GMRF variants under different levels of sparsity that I suggested, summarized the results in the response and will reflect them in the appendix of the paper. Certain points around (1) the contribution's significance and (2) the relation between the SVD-based constraint basis construction and other decomposition methods remain unresolved; however, the authors claim that further clarifications on these points will be included in the revised version of the paper. Therefore, I decided to increase my initially assigned score from 5 to 6 (Marginally above the acceptance threshold).
limitations_and_societal_impact: The authors claim that the rows of A can be split into m sub-matrices (blocks) such that each pair of blocks have no common non-zero columns; and then the SVD sub-matrices can be computed separately. I am wondering if the authors have investigated other approaches for the same purpose (e.g., block decomposition methods such as the block SVD power method)? If so, I would encourage the authors to briefly discuss this in their response.

The specifics of the covariance-based method are not explained nor is it disclosed which particular algorithm was used. Moreover, no comparison to sparse inverse covariance estimation methods has been performed. In that regard, the proposed GMRF methods are compared solely to other exact methods. In some cases, an approximation might exhibit sufficient performance, while being more efficient.

A more thorough experimental evaluation is needed. The main limitations in this regard are summarized as follows:
There is an analysis on how the number of observations or basis functions affect the RMSE and the sampling/prediction time. However, there is no analysis on how any of the proposed GMRF variants performs under different levels of sparsity. Has such an experiment been conducted? If so, I would encourage the authors to elaborate on their observations.

Too many assumptions are made in the synthetic data generation process. I am wondering if the experiments with GMRF with hard constraints have been repeated for other values of $k^2$, $\phi$, $\alpha$  (other than the [0.5, 1, 2] setting)? Moreover, in the experiments with the constrained Gaussian processes, $\alpha$ and $\sigma_2$ are simply fixed to $0.01$ and $10^{-4}$, respectively, with no explanation.

No experiments on real-world regression datasets have been conducted, particularly in the  case of the GMRF variant for Gaussian process regression.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces efficient methods for GP inference under the Markov assumption when conditioning on sparse linear combinations. The approach relies on astute changes of basis. It assumes that the matrix A representing the linear mapping involved in the conditioning can be represented in block diagonal form, enabling numerical savings in the resulting SVD. Decomposing the finite dimensional space of interest appropriately also enables enjoying elegant and practical results, as illustrated by their application to GP/GMRF modelling under hard and soft (sparse) constraints. A noticeable fact about the presented approach ist hat it also applies to intrinsic GMRFs. 
main_review: This is a neat contribution touching upon computational spatial statistics and Gaussian Process modelling. The main approach is quite simple yet potentially very useful in GP applications, as illustrated at the end of the paper. The paper is written in a quite formal way, which I personally apreciate, but could make the reading not so easy to part of ist potential readership. To take a simple example, while it is of interest to tackle the intrinsic case it might be valuable to motivate more in which circumstances it could be of practical use. Also, there is room for better motivating the relevance of the sparse constraint assumption: when it practice is this assumption met / reasonable to assume vs when is it not; also in examples in could be worth stressing more to what extent the constraints are sparse and how the matrix A could actually be refactored in simpler form. What if the constraints are not exactly sparse (but block diagonal up to very small terms outside of blocks)? 

A few additional comments along the pages follow: 
•	One speaks of fields but from Equation (1) one works with a random vector (n coordinates). 
•	I am not fond oft he hat notation as it suggests estimation. Better use tilda for instance? 
•	In what sense is Q^-1 unbounded? You mean Q^-1 has 0 eigenvalues, right? 
•	What is k0 in Assumption 1? Is it related to something else or named on the spot? 
•	Should curly C and U be vectors rather than sets as the order matters? 
•	Unless the number of authors is very large I would avoid „et al.“ in the references 

Post-discussion: thank you to the authors for their responses. I maintain my score. 
limitations_and_societal_impact: Ok
review_title: null

Meta-review: Following reviewers discussion, I recommend accepting the paper under the condition that the authors will explain that its main contributions are applications for the projective clustering problem  in probability/statistics, and cite the relevant existing solutions from different fields (coresets in computational geometry, subspace clustering in DB, dictionary learning in signal processing). It should also be clarified that the suggested solution is given as a simple and possibly inefficient solver of projective clustering for the special case where no noise exists (the points lie on the subspace).
In this case, the paper can serve as an interesting bridge between the CS, ML and statistics community.
    

Decision: Accept (Poster)