Rapid Grassmannian Averaging with Chebyshev Polynomials

Thank you for your review. We will try to better motivate the paper with more examples of practical applications. Here is a brief overview of some applications we intend to include and elaborate upon:

• Covariance Estimation in Array Processing
• Principal Component Analysis
• Low-Rank Matrix Completion
• Distance/Metric Learning
• Multi-Task Feature Learning
• Subspace Clustering

Regarding the "Grassmann Averages for Scalable Robust PCA" paper, we will incorporate this into our Related Work section. We will also attempt to improve the “hand-holding” when detailing our algorithm.

To address your questions individually,

• Can you clarify what is meant by "QR" in the first equation of Sec. 3.3? ...

The function returns the Q matrix from a QR factorization. We assumed the notation would be clear from the dimension of the returned quantity and context, as we have seen similar notation used in the literature, however we will add an explicit description to the paper to avoid any confusion.

• Can you provide a citation for "StableQR"?

The StableQR algorithm was a simple fix we came up with to mitigate the pitfalls of standard QR implementations, there is no citation.

• In the last experiment, you compute a Frechet mean ...

The chordal distance is only used for cluster assignment (each subspace is assigned to its closest cluster center w.r.t. the Grassmannian chordal distance). The Frechet mean uses Grassmannian logarithm/exponent maps as per usual.

We can change this to just use the normal metric since that simplifies the explanation. I used chordal since it does nearly the same thing and there are a lot of points to assign to cluster, so for prototyping I wanted it to be quick.

Thank you for your review. To address your points individually,

• The contribution at the technical level is incremental, in my opinion...

Chebyshev polynomials indeed have many known special properties causing them to appear often in mathematics, however we believe the assessment of Theorem 1 as “basic” may be an underestimation. To the best of our knowledge, this result has not been previously established. Our primary contributions are proving the independence of solution to upper threshold $\beta$, proving under the constraint of a fixed root, and the recognition that the modified variants are well-approximated for arbitrary order via a recursive process. The proof of Theorem 1 allows us to confidently claim that our algorithm will outperform any other polynomial-based algorithm (e.g. DeEPCA) provided $\alpha$ is chosen appropriately.

While specific problems such as decentralized PCA have been studied thoroughly in the past, our paper provides an efficient algorithm for the generalized problem of averaging points on a Grassmannian. Algorithms of this generalized form have been studied less, and as such we believe there is merit to providing a more versatile, general solution.

• The assumption on the dual-banded spectrum is also not new...

We agree that the concept of dual-banded spectra is not new, nor do we intend to claim it as so; we hope this did not come across improperly in our paper. If there was a specific region or statement in our paper that improperly conveyed this message, please point it out to us so we may correct it. What we intend to claim in our paper is that the problem of Grassmannian averaging also involves such dual-banded matrices.

Thank you for your reference to the AISTATS paper. While said paper also mentions dual-banded matrices, it is considering them from a very different perspective, that of the structure of Hessian matrices in the context of deep learning problems. Critically, their dual-banded consideration is much less general than ours (e.g. they require the bands be of equal size, we make no such restriction) and focuses on relevance to step sizes in iterative descent algorithms. The dual-banded assumption is not as critical to our analysis; our Theorem 1 establishes that indeed only the size $\alpha$ of the lower band impacts our algorithm’s parameters. For these reasons, we do not believe this should be viewed as a shortcoming of our paper.

• From a practical viewpoint, the proposed method performs ...

In Section 5.1, we indeed show that our algorithm provides a significant advantage. For instance, Figure 2(a) shows our method beating all other baselines by orders of magnitude after 30 rounds of communication. Table 1 shows our method solves problems in less time than all other baselines for all but one numerical tolerance. If your claim is that the convergence rate of our algorithm is not better than that of the most competitive baseline, DeEPCA, (both appear to converge linearly) we believe this ignores the practical consideration of simple runtime; a faster algorithm is preferable to a slower one, all else being equal.

• The algorithm listings (Algorithms 1 and 2) are highly repeated.

We will consider delegating one to the appendix in the revision.

• Section 5.2 is disconnected from ...

The experiments of Section 5.2 were intended to present results of our algorithm applied to real world data. Our algorithm is intended to be a general solution to the problem of averaging points on a Grassmannian, one which may be used as an intermediate step to solve higher-level problems such as clustering on a dataset. We will try to motivate this better in the revision.

[Part 2]

• Eq. 1: ...

We can do this.

• Could you elaborate on the connection between Theorem 1...

Could you provide a more specific question? Equioscillation is considered in the appendix, mainly Definition 1, Lemma 3, and Lemma 4. Whether or not the solution presented in Theorem 1 is the best polynomial approximation to the step function is an interesting quandary, and one we pondered in the process of writing this paper. Essentially, we have to first define what we mean by “best,” for which we can imagine several distinct reasonable criteria. If by “best” we mean minimizing the ratio of equation (2), then the answer is yes and this is the result of Theorem 1. We may include some additional language in the revision to this effect.

• Please explain how the DeEPCA ...

This will be addressed in the revision. In short, we use the fixed-size bases $U_m$ as the data matrices input to the DeEPCA algorithm. We also replace the SignAdjust procedure with StableQR.

• Line 172: ...

We can include language to explain why the QR factorization need only be applied at the end. Aside from this, we believe line 172 should follow fairly straightforwardly from line 168; please let us know if there are other points of confusion we should address here.

• Line 198: ...

We will try to be more explicit here that the values exist, but are estimated heuristically in practice.

• Figure 1: ...

This will be addressed in the revision.

• Line 264: ...

This will be addressed in the revision.

• Table 1: ...

Hypercube; this will be addressed in the revision.

• Line 438: ...

The true IAM is computed by computing the leading eigenvectors of $\bar{P}$ directly using the standard torch.linalg.eigh function in python. We will include timing for this operation in the revision.

• Section 5.2: ...

It does not, it indeed tests the centralized variant.

• $\alpha$ is used ...

This choice was made to align with the notation of the papers cited in Section 5. We will fix this in the revision.

• Line 51: ...

This will be addressed in the revision. In short, computing the IAM can be thought of as a two-step process: first compute a Euclidean average, second project back onto the manifold. This sentence was just addressing the fact that in a decentralized setting, once all agents have computed the Euclidean average, the projection operation may be performed locally without further inter-agent communication.

• Line 62: ...

We will try to make this more clear in the revision. In short, in the space of iterative power method-like polynomial algorithms, yes. If one chooses $\alpha$ appropriately, then our algorithm will converge faster than any other such algorithm, e.g. DeEPCA.

• Line 72: ...

This will be addressed in the revision.

• line 377: ...

It is a parameter that represents a regularization term penalty from the “A riemannian gossip approach to subspace learning on grassmann manifold” paper by Mishra et. al. We will try to clarify that these parameters are using the namespace of the paper from which the algorithm is defined.

[Part 1]

Thank you for your review. To address your points individually,

• Importance of Decentralized Grassmannian Averaging: ...

We will attempt to better motivate situations where decentralization is essential. Briefly, these are situations when the data is sufficiently large, must respect some privacy model, or the algorithm is run on edge-devices. Around line 53 we attempted to detail how operating on sufficiently large data may necessitate the use of distributed algorithms, but we agree this could be elaborated upon. Additionally, we intend to include further concrete applications; these include covariance estimation in array processing, PCA, low-rank matrix completion, distance/metric learning, multi-task feature learning, and subspace clustering.

• Comparison and Relation to Existing Literature: ...

We will include these considerations in the revision.To briefly address the question, methods such as Chebyshev-Davidson tend to be hard to decentralize due to intermediate computations of quantities such as solutions to inverse problems and eigenproblems. In the specific case of Chebyshev-Davidson, the solved problem is actually semantically different as well: extract specific non-leading eigenpairs. Since our algorithm, from a spectral perspective, seeks only to learn only the span of the leading eigenvectors, we can compute this more efficiently.

• Section 3.1: ...

We will address and elaborate upon this in the revision. To address these questions briefly,

• The invariance of choice of representative comes from the fact that $(U_m Q) (U_m Q)^T = U_m U_m^T$ for any square orthogonal matrix $Q$.
• The eigenvector solution comes from the fact that problem (1) is essentially a type of Procrustes problem (see “Procrustes Problems” by John Gower and Garmt B Dijksterhuis). A proof will be given in the revision.

• Section 3.2: ...

To address these concerns:

• What is average consensus (AC)? - Average consensus is used frequently in the literature of decentralized algorithms, so we thought introducing it with reference as we did in line 137 was sufficient: “Average consensus (AC) is a useful primitive in decentralized optimization to quickly approximate the average of real numbers in a decentralized manner (Nedic & Ozdaglar, 2009).”
• Why can’t AC be used directly to approximate (1)? - Line 139 states “Unfortunately, the non-convex manifold structure of Gr(N, K) precludes us from efficiently applying AC directly to solve eq. (1)”; if a set is not convex, then it is a fact that the average of points from this set may not necessarily be a member of the set. So AC would not compute an average on the manifold.
• Most importantly, why is it sufficient to approximate the lower dimensional $PX$? In what way does this guarantee an approximation of $P$? - This is elaborated upon later in Section 3.3, as power methods only require matrix-vector products to function. We will try to better motivate this in Section 3.2 however to prevent prematurely confusing the reader. We will attempt to clarify these points in the revision.

• Section 4.1: ...

We will attempt to clarify this in the revision. Briefly, our method is akin to noise cancellation. We start with a matrix like $\bar{P}$, then perturb its eigenvalues to try to “cancel” out the trailing eigenvalues relative to the leading eigenvalues. Any collection of $K$ vectors applied to such a matrix would then approximately lie in the span of the leading eigenvectors $[V]$. Since polynomials applied to matrices preserve eigenvectors while applying the polynomial to each eigenvalue, identifying an ideal polynomial in the sense of Theorem 1 leads to convergence on $[U]$.

• Section 4.2: ...

It is an experimental observation, partially justified visually with Figure 1. We will make this clear in the revision.

• Experimental Results Are Limited: …

To address these points succinctly, we will rework things to try to address all criticisms mentioned. To directly address one point: if optimally tuned, our method DRGrAv will converge even quicker. However, we believe being able to optimally tune DRGrAv is not realistic in practice, hence the use of a realistic heuristic tuning. Baseline methods were optimally tuned to ensure that our performance was not merely a consequence of poor tuning of the baselines. In practice, one would have to heuristically tune these as well; in some sense, this makes the performance of our algorithm look artificially poorer by comparison in these experiments. However, we believe this approach should give readers confidence the comparison is not “cherry-picked”.