I. INTRODUCTION

M ODERN high-dimensional datasets are often formed by combining samples acquired from multiple sources, where the sources have heterogeneous quality and cost. Namely, some sources are noisier than others, and acquiring samples from higher-quality (less noisy) sources is typically more costly (whether in time or energy). For example, air quality data are currently acquired using both low-cost consumergrade sensors and high-precision instruments that are carefully maintained by government agencies [1], [2]. In general, one can imagine deploying sensor networks with a heterogeneous mix of sensors of varying cost and corresponding quality.

One often seeks to find underlying low-dimensional structure revealed by the data. Principal component analysis (PCA) is a foundational technique for this task, and it is a workhorse method in modern signal processing. For example, PCA has been used to identify sources of air pollution from air quality data [3], [4]. However, conventional PCA is not designed for samples with heterogeneous amounts of noise; it treats all samples uniformly. A weighted PCA that gives noisier samples less weight is a more suitable method, and recent work [5] derived optimal weights for this scenario. The resulting optimally D. Hong was supported in part by NSF Graduate Research Fellowship DGE 1256260, NSF Grant ECCS-1508943, NSF BIGDATA grant IIS 1837992, the Dean's Fund for Postdoctoral Research of the Wharton School, and NSF Mathematical Sciences Postdoctoral Research Fellowship DMS 2103353. L. Balzano was supported in part by DARPA-16-43-D3M-FP-037, NSF CAREER award CCF-1845076, NSF Grant ECCS-1508943, and ARO YIP Award W911NF1910027. D. Hong is with the Department of Electrical and Computer Engineering, University of Delaware, Newark, DE 19716 USA (email: hong@udel.edu). L. Balzano is with the Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, MI 48109 USA.

weighted PCA optimally downweights noisier samples to best recover the underlying low-dimensional components.

This paper tackles the following question: what is the best way to acquire samples for optimally weighted PCA? Namely, given multiple sources of data, how many samples should be acquired from each source to maximize the performance of optimally weighted PCA? Naturally, the more data, the better the performance of optimally weighted PCA. However, in practice there are typically constraints. In particular, acquiring samples often has associated costs, resulting in constraints of the following form:

where n 1 , . . . , n L are the number of samples acquired from each of L available data sources, κ 1 , . . . , κ L are the per-sample costs for each source, and τ is the corresponding budget. Each type of cost (e.g., in time or energy) adds a constraint of this form. Moreover, each source often has a finite quantity of samples it can provide, resulting in additional constraints:

where q 1 , . . . , q L are the quantity of samples that each source can provide. Both (1) and ( 2) are linear constraints, so can be captured in general as follows:

where n := (n 1 , . . . , n L ) is the number of samples to acquire from each source, denotes entrywise inequality, and A and b define the constraints. The goal is to choose n to maximize the performance of optimally weighted PCA subject to the constraints (3). A number of recent works have studied the topic of PCA for high-dimensional heterogeneous-quality data [5]- [21], but they generally focus on how to use the given data rather than on how to acquire it. The question of how to best acquire data falls within the field of experimental design, for which there are numerous works (many more than can be reviewed here, see, e.g., the textbooks [22]- [27]). However, to the best of our knowledge, the question we consider here (optimal design for optimally weighted PCA) has not yet been addressed. This paper tackles this open problem.

Section II describes the data model and reviews optimally weighted PCA. Section III states the main result: a characterization of the optimal sample acquisition designs that enables us to develop a computationally efficient algorithm for finding an optimal design. Sections IV and V demonstrate the method through an illustrative example and case studies. Section VI concludes the paper with a proof of the main result. II. DATA MODEL AND OPTIMALLY WEIGHTED PCA This paper considers acquiring n 1 , . . . , n L samples from L data sources with associated noise variances v 1 , . . . , v L > 0, where the sources share k underlying orthonormal components u 1 , . . . ,

Precisely put, we model the data block Y ℓ ∈ C d×n ℓ obtained by acquiring n ℓ samples from the ℓth source as in [5]:

where d is the number of features,

is a deterministic factor matrix common to all the sources, • Z ℓ ∈ C k×n ℓ is a coefficient matrix with IID entries that have zero mean and unit variance, • E ℓ ∈ C d×n ℓ is a noise matrix with IID entries that have zero mean and variance v ℓ > 0, and the noise further satisfies a technical condition: bounded a-th moment for some a > 4, i.e., sup i,j E|(E ℓ ) i,j | a < ∞. 1Since the data sources have different amounts of noise, one should use a weighted PCA to account for their heterogeneous quality. Given weights w := (w 1 , . . . , w L ), weighted PCA estimates the ith underlying component u i as

i.e., ûi (w, Y ) is the ith leading eigenvector of the w-weighted sample covariance matrix. Naturally, one wants to use weights that maximize the recovery of u i . Such weights were recently found in [5]. Namely, asymptotically optimal weights w i and their corresponding asymptotic performance r i are given by

r i when the number of features d and the numbers of samples n 1 , . . . , n L are all sufficiently large. Specifically, r i is the optimal performance in the limit where d and n 1 , . . . , n L all grow to infinity with fixed aspect ratios n ℓ /d; 3 see [5] for further details. This highdimensional regime corresponds to many big data settings.

Note that the asymptotic performance of optimally weighted PCA is component-specific, so the optimal sample acquisition strategy may differ from component to component. Note also that computing r i requires either knowing the signal and noise variances λ i and v 1 , . . . , v L a priori or estimating them from data, e.g., using the methods described in [5,Example 7.2].

III. MAIN RESULT: OPTIMAL SAMPLE ACQUISITION

The problem is to choose n := (n 1 , . . . , n L ), the numbers of samples to acquire from each source, to optimize the performance (7) of optimally weighted PCA subject to linear constraints on n. Precisely put,

where R + denotes the set of nonnegative real numbers, is entrywise inequality, A and b define the linear constraints, and we have made the dependence of r i on n explicit. Throughout this paper, we will assume that A and b define nontrivial constraints in the sense that {n ∈ R L + : An b} is not only nonempty but also bounded. Otherwise, one can of course take n → ∞ and achieve perfect performance. However, one can always expect to have nontrivial constraints in practice since collecting and processing samples takes both time and space.

Solving the optimization problem ( 8) is nontrivial because r i (n) is not given as an explicit expression in n. It is instead defined implicitly in (7) via the roots of a rational function with coefficients that depend on n. Furthermore, r i (n) is a nonlinear function of n. Fortunately, as our main result shows, solutions occur at extreme points of the constraint region.

Theorem 1 (Optimal sample acquisition). The optimal sample acquisition problem (8) has a solution (not necessarily unique) that is an extreme point of the constraint polyhedron

Remark 1 (Non-integer values). Note that we have relaxed n to have nonnegative real-valued (rather than integer-valued) entries. This relaxation should have little impact in the highdimensional regime of interest; simply round the solution of (8) to obtain integer numbers of samples to acquire. One can also avoid this technicality by instead formulating (8) in terms of the (already real-valued) asymptotic aspect ratios n ℓ /d.

It follows from Theorem 1 that global optimization of (8) can be accomplished by simply choosing the best among the extreme points of P (a finite set). This leads naturally to the following simple and efficient algorithm.

Algorithm 1 Sample acquisition optimization

choose best candidate 4: return n Remark 2 (Computing extreme points). The extreme points of P in Line 2 of Algorithm 1 can be efficiently obtained from (A, b) using standard polyhedral software; see, e.g., [29], [30].

The runtime of Algorithm 1 can grow dramatically when the number of sources is large; developing algorithms that scale better is an interesting direction for future work. That said, we found that cases with tens to even hundreds of constraints can often complete in fractions of a second when the number of sources is moderate (e.g., around ten or less), as is the case in many applications.

IV. ILLUSTRATIVE EXAMPLE

We illustrate our main result (Theorem 1) and the resulting algorithm (Algorithm 1) with the following example of two sources with limited quantities and a single budget constraint. Example 1. Consider acquiring d = 100 dimensional samples from L = 2 sources with an underlying component u i having signal variance λ i = 10, where • source 1 samples have noise variance v 1 = 2, a limited quantity of 180 samples, and a per-sample cost of 1, • source 2 samples have noise variance v 2 = 1, a limited quantity of 90 samples, and a per-sample cost of 3, and the total budget is 300. This yields the linear constraints defined by A =   1 0 0 1 1 3   , b =   180 90 300   , illustrated in Fig. 1.

An b

To find the optimal sample acquisition, we proceed according to Algorithm 1 (based on Theorem 1): 1) Find the extreme points E of P = {n ∈ R L + : An b}: E = {(0, 0), (0, 90), (30,90), (180, 40), (180, 0)}.

2) Evaluate r i (n) for each n ∈ E and choose the best:

Note that (0, 0), (0, 90), and (180, 0) can all be skipped because either n 1 or n 2 can be increased for each choice, trivially yielding an improvement in performance. The optimal sample acquisition n = (180, 40) corresponds to collecting all the available samples from source 1 (i.e., all the cheaper, noisier samples that are available) then spending the rest of the budget on samples from source 2 (i.e., the more costly, higher quality samples).

V. CASE STUDIES AND INSIGHTS

The following case studies demonstrate Theorem 1 through a few interesting scenarios that provide some new insights into optimal sample acquisition for optimally weighted PCA.

A. Optimal sample acquisition under a single constraint

Suppose the constraint region reduces to a single constraint. For example, consider the setting of Example 1 but with over 300 source 1 samples and over 100 source 2 samples available. In this case, the constraints reduce to the single constraint

with three extreme points E = {(0, 0), (300, 0), (0, 100)}. As before, (0, 0) can be skipped, so either (300, 0) or (0, 100) is optimal. Namely, it is optimal to use only one source. In this case, (300, 0) is better, i.e., it is optimal to acquire samples from only the noisier less-costly source. Indeed, as the following corollary states, it is always optimal to use only one source when there is effectively one constraint.

Corollary 2 (Optimality for a single constraint). If the constraint region reduces to a single constraint, i.e., ∃ a∈R L ,b∈R P = {n ∈ R L + : a n b}, then the optimal sample acquisition problem (8) has a solution using only one source, i.e., a 1-sparse solution of the form n = (0 ℓ-1 , b/a ℓ , 0 L-ℓ ) where ℓ ∈ {1, . . . , L}. (10) Corollary 2 follows straightforwardly from Theorem 1 by observing that the nonzero extreme points are of the form (10).

While this result is perhaps natural given Theorem 1, note that it was not obvious a priori. It would have been natural to expect the optimal sample acquisition to require a precise mix of both high-quality high-cost samples and low-quality low-cost samples, especially given the nonlinearity of r i (n).

B. Optimal sample acquisition for multiple components

The performance of optimally weighted PCA depends nontrivially on the signal variance, so may vary from component to component. Thus, the optimal sample acquisition strategy could also differ among components. However, unlike the optimal weights (6), the optimal sample acquisition can also be the same for components that have different signal variances.

Consider the setting of Example 1 but where we sweep λ i from 1 to 10. Fig. 2 shows the optimal sample acquisition strategies computed by Algorithm 1 (omitting the small interval λ i ∈ [1, 1.013] where the optimal performance was zero). Notably, the optimal sample acquisition strategy is constant over large intervals. Thus, there can be a single optimal strategy for all the components, as long as their signal variances lie in the same interval. Interestingly, these results also suggest that the optimal strategy may be somewhat robust to potential errors in estimating the signal and noise variances.

VI. PROOF OF MAIN RESULT (THEOREM 1)

Let Q be the solution set for the optimization problem (8), and let ρ be the associated optimal value, i.e.,

The goal is to show that

Note first that (12) holds trivially if ρ = 0 because Q = P in that case and P always has at least one extreme point (by [31,Theorem 2.6]) since it is a nonempty bounded polyhedron (by assumption). So it remains to show (12) for ρ > 0.

The proof for ρ > 0 proceeds in two stages: (i) show that Q has extreme points, and (ii) show that extreme points of Q are also extreme points of P. (12) then follows immediately.

Stage 1. This stage shows that Q has extreme points when ρ > 0. To begin, we establish the following properties of Q: (nonempty) r i (n) is a continuous function on the domain P and P is both compact (it is a bounded polyhedron) and nonempty. Thus, r i (n) attains its maximum ρ on P, and Q is nonempty. (bounded) Q ⊆ P and P is bounded (by assumption), so Q is also bounded. (polyhedron) Note that

where

because R i,n (x) has exactly one root in the interval (0, 1) unless L ℓ=1 (n ℓ /d)(λ i /v ℓ ) 2 ≤ 1, in which case it has no roots in the interval. Thus, Q can be expressed as follows:

where the first line follows from the definition of Q, the second line follows from (13), the third line follows by substituting (14), and the fourth line is rearranging. It follows from the form of (15) that Q is a polyhedron. Hence, Q is a nonempty bounded polyhedron, and it follows from [31,Theorem 2.6] that Q has at least one extreme point.

Stage 2. This stage shows that any extreme point of Q must also be an extreme point of P when ρ > 0. We proceed by proving the contrapositive, i.e., that any non-extreme point of P cannot be an extreme point of Q.

Note that the statement trivially holds for any non-extreme point of P that is not in Q. So, it remains to consider the case where the non-extreme point of P is in Q

Diagram illustrating the relative positions of s, t, n , and t. Namely, n is between s and t, and t is between s and n .

be a non-extreme point of P. Then, there must exist points s, t ∈ P \ {n } and γ ∈ (0, 1) so that

Moreover, since r i (n) is continuous and P is convex, we can always choose the points s and t to be close enough to n so that r i (s), r i (t) > ρ /2. Without loss of generality, suppose that r i (s) ≤ r i (t). Since n maximizes r i (n), this yields

Thus, it follows by the intermediate value theorem that r i (n) takes on the value ρ := r i (t) at a point between s and n , i.e., there exists some γ ∈ [0, 1] so that r i ( t) = ρ, where t := γ

Note next that s, t, n , and t are collinear (as shown in Fig. 3), so it follows that n and s are both affine combinations of t and t. Specifically, solving ( 16) and ( 18) for n and s yields n = µ • t + (1 -µ) • t, s = μ • t + (1 -μ) • t, (19) where µ = γ/(γ + γ -γγ) and μ = 1/(γ + γ -γγ).

Substituting the first equation of ( 19) into (14) yields

Likewise, substituting the second equation of ( 19) into ( 14) yields

Since r i ( t) = r i (t) = ρ, it follows that R i, t( ρ) = R i,t (ρ) = 0 and hence R i,n (ρ) = R i,s (ρ) = 0. Noting that ρ > ρ /2 > 0 and applying (13) then yields that r i (n ) = r i (s) = ρ, and as a result

i.e., r i (s) = r i (t) = ρ so s, t ∈ Q \ {n }, implying that n is not an extreme point of Q and completing the proof.