Line Cover and Related Problems

First, we show that Line Clustering is $\mathrm{W}[1]$-hard when parameterized by the number $k$ of lines in the solution. Our reduction also implies a lower bound based on the Exponential Time Hypothesis (ETH).

We consider Theorem 1 to be particularly interesting for several reasons. First, it underscores a clear contrast between Line Cover– which is $\mathrm{FPT}$ when parameterized by $k$ – and Line Clustering. Second, Line Clustering is closely related to $k$-means clustering, where instead of fitting $k$ lines, one seeks $k$ points (i.e., zero-dimensional subspaces) that best fit the data in the $L_2$ norm. Notably, the parameterized complexity of $k$-means clustering in ${ℝ}^2$ (with parameter $k$) remains a longstanding open question [14].

Our second lower bound concerns Hyperplane Cover. Since in ${ℝ}^2$ this problem is equivalent to Line Cover, which is $\mathrm{NP}$-complete, we know that the problem is $\mathrm{Para}-\mathrm{NP}$-complete when parameterized by $d$. On the other hand, by the work of Langerman and Morin [31], Hyperplane Cover is $\mathrm{FPT}$ when parameterized by $k$ and $d$. Theorem 2 refines this complexity picture by proving that Hyperplane Cover is $\mathrm{W}[2]$-hard when parameterized by $k$ alone (and $d$ is large compared to $k$).

The lower bounds provided in Theorem 1 rule out the existence of an algorithm for Line Clustering of running time $n^{o(k)}$. We complement this lower bound by providing an algorithm of running time $n^{O(k)}$. The algorithm is provided for the more general problem Projective Clustering. To the best of our knowledge, this is the first $\mathrm{XP}$ algorithm for Projective Clustering parameterized by $k$ and $d$.¹¹1As is common in computational geometry, we assume a real RAM model for computation. Note that $r\le d$.

Since $k$-Means Clustering is the (very) special case of Projective Clustering with $r=0$, Theorem 3 significantly extends the work of Inaba et al. [27], who gave an algorithm for $k$-Means Clustering running in $n^{𝒪(kd)}$ time. It is also worth noting that the tools we use to prove Theorem 3 are quite different from those employed by Inaba et al., who relied on weighted Voronoi diagrams. In contrast, the proof of Theorem 3 leverages a fundamental result from computational algebraic geometry, which computes a set of sample points that meets every realizable sign condition of a family of polynomials restricted to an algebraic set.

Line Cover is NP-hard and APX-hard [4, 9, 33]. A number of results in parameterized complexity and kernelization in the literature is devoted to Line Cover and Hyperplane Cover. Langerman and Morin [31] proposed an $k^{dk+d}{n}^{𝒪(1)}$-time algorithm for Hyperplane Cover. Later, the running time was improved by Wang et al. [45] to $\frac{k^{(d-1)k}}{{1.3}^k}{n}^{𝒪(1)}$. Afshani et al. [1] gave an algorithm of running time $O(2^n)$. They also improved on the $\mathrm{FPT}$ algorithm for Hyperplane Cover in ${ℝ}^3$. Their improved algorithm runs in ${\left(\frac{C{k}^2}{\log k^{1/5}}\right)}^k{n}^{𝒪(1)}$ time. They also presented a ${\left(\frac{Ck}{\log k}\right)}^k{n}^{𝒪(1)}$-time algorithm for Line Cover. Kratsch et al. show that the well-known $𝒪(k^2)$ kernel for Line Cover is tight under standard complexity assumptions [29]. A similar result exists for Hyperplane Cover [8].

Due to its importance in theory as well as applications, the study of Projective Clustering enjoys a long and rich history. Various approaches have been used to solve Projective Clustering: kernel sets [2, 23], coresets [23, 41], total sensitivity [21, 30, 41], and dimension reduction via sampling [16, 39].

A parameterized problem is a language $Q\subseteq {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$, where ${\mathrm{\Sigma }}^{\ast }$ is the set of strings over a finite alphabet $\mathrm{\Sigma }$. Specifically, an input of $Q$ is a pair $(I,k)$, where $I\in {\mathrm{\Sigma }}^{\ast }$ and $k\in \mathbb{N}$; $k$ is the parameter of the problem. A parameterized problem $Q$ is fixed-parameter tractable ($\mathrm{FPT}$) if it can be decided whether $(I,k)\in Q$ in $f(k){|I|}^{𝒪(1)}$ time for some computable function $f$ that depends only on the parameter $k$. The parameterized complexity class $\mathrm{FPT}$ consists of all fixed-parameter tractable problems. A parameterized problem $L\in {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$ is called slice-wise polynomial (XP) if there exists an algorithm $𝒜$ and two computable functions $f,g:\mathbb{N}\to \mathbb{N}$ such that, given an instance $(I,k)\in {\mathrm{\Sigma }}^{\ast }\times \mathbb{N}$, the algorithm $𝒜$ correctly decides whether $(x,k)\in L$ in $f(k)\cdot {|I|}^{g(k)}$ time. The parameterized complexity class containing all slice-wise polynomial problems is called $\mathrm{XP}$.

The $𝖶$-hierarchy is a collection of computational complexity classes; we omit the technical definitions here. It is widely believed that $\mathrm{FPT}\ne \mathrm{W}[1]$, and hence, if a problem is hard for a class $\mathrm{W}[i]$ with $i\ge 1$, then it is considered to be fixed-parameter intractable. For a detailed introduction to parameterized complexity, we refer readers to the textbooks by Cygan et al. and by Downey and Fellows [15, 18]. We also provide conditional lower bounds by making use of the following complexity hypothesis formulated by Impagliazzo, Paturi, and Zane [26].

Exponential Time Hypothesis (ETH): There is a positive real $s$ such that 3-CNF-SAT with $n$ variables and $m$ clauses cannot be solved in time $2^{sn}{(n+m)}^{𝒪(1)}$.

We give a reduction from Regular Multicolored Independent Set. Therein, one is given a graph $G=(V,E)$ and a partition of the $n$ vertices into $V_1,V_2,\mathrm{\dots },V_{\mathrm{\ell }}$ (often referred to as colors of vertices) such that $|V_i|=\nu =n/\mathrm{\ell }$ for each $i\in [\mathrm{\ell }]$ and each vertex $v$ has exactly $q$ neighbors (none of which have the same color as $v$). The question is whether there exists an independent set containing exactly one vertex of each color. It is known that Regular Multicolored Independent Set is $\mathrm{W}[1]$-hard parameterized by $\mathrm{\ell }$ [15, Proposition 13.5.] and cannot be solved in $n^{o(\mathrm{\ell })}$ time unless the $\mathrm{ETH}$ fails [11]. We will assume without loss of generality that $\nu$ is divisible by $4$, $\nu >{\mathrm{\ell }}^3$, $\mathrm{\ell }>10$, and $V_i=\{w_1^i,w_2^i,\mathrm{\dots },w_{\nu }^i\}$.

The crucial step is a polynomial gap-reduction that constructs an instance $(S,k,B)$ of Line Clustering where $S$ is a multiset of points in ${ℝ}^2$ (that is, we allow points to have the same coordinates) with integer coordinates and $k=2\mathrm{\ell }+4$ with the following property:

• $\mathrm{■}$

  If the original instance of Regular Multicolored Independent Set is a yes-instance then there are $k$ lines such that the sum of squares of distances from all points in $S$ to the closest line in the solution is at most $B$.

• $\mathrm{■}$

  Otherwise, if we have a no-instance of Regular Multicolored Independent Set then for any $k$ lines, the sum of squares of distances from all points in $S$ to the closest line is at least $B+2$.

We use this gap-reduction to argue that Line Clustering is W[1]-hard when $S$ is a set of points. For this, we apply the gap-reduction to an instance $G$ of Regular Multicolored Independent Set and denote by $(S,k,B)$ the obtained instance of Line Clustering where $N$ is the number of points. Let $\delta =1/3BN$. Then for every inclusion maximal multiset of points $X\subseteq S$ with the same coordinates $(x,y)$, we construct a set of $|X|$ points $Y_X$ with distinct rational coordinates such that every point $p\in Y_X$ is at distance at most $\delta$ from $(x,y)$. As $|X|\le N$, $Y_X$ can be constructed in such a way that the denominators of the coordinates of each point are at most $N/\delta =3B{N}^2$, and the absolute values of the numerators are at most $N+3B{N}^2\max \{|x|,|y|\}$. Thus, the encoding of the coordinates of the point of $Y_X$ is polynomial. Notice also that the sets $Y_X$ constructed for distinct $X\subseteq S$ are disjoint. We denote by $S^{\prime }$ the obtained set of distinct points ${ℝ}^2$, and let $B^{\prime }=B+1$.

Consider the instance $(S^{\prime },k,B^{\prime })$ of Line Clustering. Suppose that $G$ has a multicolored independent set. Then, there are $k$ lines such that the sum of squares of distances from all points in $S$ to the closest line is at most $B$. Suppose that a point $p\in S$ is on distance $h$ from the closest line. Because $p$ is at distance at most $\delta$ from the corresponding point $p^{\prime }\in S^{\prime }$, the distance from $p^{\prime }$ to the closest line is at most $h+\delta$. Since the distance between each point of $S$ and the closest line is at most $B$, ${(h+\delta )}^2=h^2+2h\delta +{\delta }^2\le h^2+2B\delta +{\delta }^2$. By taking the sum over all points in $S^{\prime }$, we obtain that the sum of squares of distances from the points in $S^{\prime }$ to the closest line is at most . Hence, $(S^{\prime },k,B^{\prime })$ is a yes-instance. Assume now that $G$ has no multicolored independent set. Then, for any any $k$ lines, the sum of squares of distances from all points in $S$ to the closest line is at least $B+2$. If a point $p\in S$ is at distance $h$ from some line then the corresponding point $p^{\prime }\in S^{\prime }$ is at distance at least $h-\delta$ from the same line. For the square of the distance, we have that it is at least ${(h-\delta )}^2=h^2-2h\delta +{\delta }^2\ge h^2-2B\delta +{\delta }^2\ge h^2-2B\delta$. This implies that for any $k$ lines, the sum of squares of distances from all points in $S^{\prime }$ to the closest line is at least $(B+2)-2BN\delta >(B+2)-1=B+1=B^{\prime }$. Thus, $(S^{\prime },k,B^{\prime })$ is a no-instance of Line Clustering. This proves that Line Clustering is W[1]-hard when $S$ is a set of points.

In the remaining part of the proof, we provide the gap-reduction for a multiset of input points. Before we present the reduction in detail, we first give a high-level overview. Our aim is to build a grid-like structure where any optimal solution contains $\mathrm{\ell }$ vertical and $\mathrm{\ell }$ horizontal lines. Each horizontal line and each vertical line correspond to picking a vertex in a solution. The aim is then to construct a set of points such that (i) for each horizontal line in the solution there is a vertical line in the solution that encodes the same vertex (to ensure that a solution selects precisely $\mathrm{\ell }$ vertices) and (ii) for each pair of horizontal and vertical lines in a solution, the corresponding vertices are not adjacent in the input graph. We do this by placing points on the intersection of two such lines whenever the two respective vertices share an edge or are two distinct vertices of the same color. Otherwise, we place a point on the horizontal line close to the intersection. Imagine for now that these points have distinct distances from a “solution line” such that no vertical line contains more than one such point. See Figure 2 for an example.

Now, any independent set of size $\mathrm{\ell }$ containing exactly one vertex from each set $V_i$ corresponds to a set of $\mathrm{\ell }$ horizontal and $\mathrm{\ell }$ vertical lines containing a maximum number of points.

With this intuition in mind, there are two main obstacles to overcome. First, we want to ensure that the solution lines are actually (almost) horizontal and vertical and second, covering a maximum number of points is different from minimizing the sum of squares of distances from each point to the closest line. We start with the second obstacle. Assume that there are two lines (one vertical and one horizontal) that is part of any optimal solution that is far enough away from the previously described set of points so that they are never the closest line to any of these points. Let $W$ be some sufficiently large (but also not too large) number. We place all vertical lines corresponding to vertices within the same set $V_i$ closer together than lines corresponding to vertices in different sets (as already indicated in Figure 2). We do the same for all horizontal lines. By making the distance $d_s$ between lines corresponding to vertices in different sets large enough, we can ensure that for any set $V_i$ any optimal solution contains one horizontal line and one vertical line that corresponds to a vertex in $V_i$ (assuming that all solution lines are horizontal or vertical). Next, we compute for each horizontal line the sum of squares of distances of all points on horizontal lines corresponding to vertices within the same set $V_i$ except for those points that lie on the vertical line corresponding to the same vertex. For a line $h$, let that number be $\varphi (h)$. Then, we place $W-\varphi (h)$ points on line $h$ at a distance of one from the vertical line that is part of any optimal solution. We also place $W$ points on each vertical line corresponding to picking a vertex at distance one from the horizontal line that is part of any solution and can now adjust the previous construction such that all points are covered by $2\mathrm{\ell }\nu$ vertical lines, that is, we no longer need to imagine that points placed because of edges in the input graph (or for pairs of vertices in the same set $V_i$) have distinct distances. See Figure 3 for an illustration of the updated construction.

We will show that these newly added points ensure that any set of $\mathrm{\ell }$ vertical and $\mathrm{\ell }$ horizontal lines that minimize the sum of squares of distances to all points are also lines that cover a maximum number of points.

Finally, we want to ensure that lines in the solution are horizontal and/or vertical. Unfortunately, we were not able to ensure this property but the following construction ensures that all solution lines are almost vertical or horizontal. Consider the construction in Figure 4 where $d_{\mathrm{\ell }}$ is much larger than $d_s$. We will show that any line that covers as many points as there are points in one row or column of the constructed point set, has to contain the points of exactly one row or one column. We will then pick a suitable number $p$, duplicate each point in the construction in Figure 3 $p$ times, and set the budget $B$ correspondingly such that any line that encodes a vertex in some set $V_i$ has a sum of squares of distances to points in the $i$^th row or column of the construction in Figure 4 that is negligible while any line that is not almost vertical or horizontal has a point in any row or column of the construction such that the distance between this point and the line alone is larger than the budget $B$. We also place a lot of vertices in the eight “corners” of the construction to ensure that there are two horizontal and two vertical lines that are part of any solution. This concludes the overview of the reduction. We now present the construction in more detail.

We start by defining $p=n^{10}$, $W=n^{30}$, $d_s=n^{40}$, $d_{\mathrm{\ell }}=n^{90}$, and the functions

We set $k=2\mathrm{\ell }+4$ and $B=n^7+(n-\mathrm{\ell })W+\mathrm{\ell }{\sum }_{i=1}^{\nu }(W+\phi (i))-\mathrm{\ell }W+\mathrm{\ell }p(n-\nu +1-q-\mathrm{\ell })$. Note that $B\le n^{32}$. We then construct a set $F$ of $8n^{90}+k^2+2k$ points as follows. We place points in a $\frac{k}{2}\times (k+2)$ grid $G_h$ where the vertical distance between points is $d_s$ and the horizontal distance is $d_{\mathrm{\ell }}$. We leave $(\mathrm{\ell }+1)d_s$ extra space between columns $k+2/2$ and $k+2/2+1$ (this is where we will place the main part of the construction depicted in Figure 3). We place $n^{90}$ points at each of the four corners of the grid (on top of the already existing point). We then repeat the process with a $(k+2)\times \frac{k}{2}$ grid $G_v$ where the vertical distance between points is $d_{\mathrm{\ell }}$ and the horizontal distance is $d_s$. We place the two grids such that the additional extra space forms a square in the middle of both grids. We call the set of all points placed so far $F$ and the vertical/horizontal lines that each go exactly through $2n^{90}+k+2$ points the fixed lines (we will show later that we can assume these four lines to be part of any optimal solution). An illustration of the points in $F$ is given in Figure 4.

Next, we construct the rest of the instance in the middle gap. We start with $\mathrm{\ell }$ bundles of $\nu$ horizontal lines each. That is, for each $i\in [\mathrm{\ell }]$ and each $j\in [\nu ]$, we define a horizontal line $h_i^j$. The height of the $\nu /2$^th line in the $i$^th bundle is equal to the height of points in $F$ in the $i+1$^st row of $G_h$. The distance between $h_i^j$ and $h_i^{j+1}$ is $3$ where $h_i^j$ is the higher line. Next, we define vertical lines $v_i^j$ and $s_i^j$ for each $i\in [\mathrm{\ell }]$ and each $j\in [\nu ]$ as follows. The $x$-position of line $v_i^{\nu /2}$ is equal to the $x$-positions of points in $F$ in the $i+1$^st column of $G_v$. The distance between $v_i^j$ and $v_i^{j+1}$ is $10n^2$ where $v_i^j$ is to the left. Line $s_i^j$ is one to the left of $v_i^j$. An illustration of these lines (and the input points we will place on these lines next) is given in Figure 5.

For each pair $w_j^i,w_{j^{\prime }}^{i^{\prime }}$ of vertices in the input graph $G$ with $i\ne i^{\prime }$, we place $p$ points on the intersection of $h_i^j$ and $s_{i^{\prime }}^{j^{\prime }}$ if $\{w_j^i,w_{j^{\prime }}^{i^{\prime }}\}\in E$ and on the intersection of $h_i^j$ and $v_{i^{\prime }}^{j^{\prime }}$ otherwise. Note that we also place points symmetrically on the intersection of $h_{i^{\prime }}^{j^{\prime }}$ and $s_i^j$ if the two vertices are adjacent and on the intersection of $h_{i^{\prime }}^{j^{\prime }}$ and $v_i^j$ if they are not. For $i=i^{\prime }$, we place $p$ points on the intersection of $h_i^j$ and $v_{i^{\prime }}^{j^{\prime }}$ if $j\ne j^{\prime }$ and on the intersection of $h_i^j$ and $s_{i^{\prime }}^{j^{\prime }}$ if $j=j^{\prime }$. Let $X$ be the set of points placed in the previous step. Note that we place exactly $np=n^{11}$ points of $X$ on each line $h_i^j$, exactly points on each line $s_i^j$, and exactly points on each line $v_i^j$. Finally, for each $i\in [\mathrm{\ell }]$ and each $j\in [\nu ]$, we place $\frac{W}{4}$ points on $s_i^j$ one above and below each of the two horizontal fixed lines (that is, we place $W$ points on each line $s_i^j$). Let $Z_v$ be the set of all of these points. Note that $|Z_v|=nW$. We also place $\frac{W+\phi (j)}{4}\ge \frac{W}{4}$ points on each line $h_i^j$ one to the left and one to the right of each of the two vertical fixed lines. Let $Z_h$ be the set of all these points. Note that $|Z_h|=\mathrm{\ell }\left({\sum }_{j=1}^{\nu }W+\phi (j)\right)$. This concludes the construction.

Since the construction can be computed in polynomial (in $n$) time as there are a polynomial number of points, all coordinates are integers and the largest distance between points is in $O(\mathrm{\ell }{d}_{\mathrm{\ell }})\subseteq \mathrm{poly}(n)$ and since $k\in O(\mathrm{\ell })$, it only remains to show correctness.

For space reasons, the proof of correctness is deferred to a full version. $◀$

We distinguish between two cases: $r=0$ and $r>0$. In the case where $r=0$, note that $n^{𝒪(dk(r+1))}=n^{𝒪(dk)}$. Moreover, the case is equivalent to $k$-Means. We can therefore use the $n^{𝒪(dk)}$-time algorithm of Inaba et al. [27].

We next explain our algorithm for the case $r>0$. We will map $k$-tuples of $r$-dimensional affine subspaces with points of a certain algebraic set. We can represent an $r$-dimensional affine subspace of ${ℝ}^d$ by a $d\times (r+1)$ matrix $𝐕$ where the first $r$ columns represent an orthonormal basis of a linear subspace of dimension $r$ and column $(r+1)$ represents the offset point. Consider the matrix space ${ℝ}^{d\times k(r+1)}$ and a matrix $𝐕\in {ℝ}^{d\times k(r+1)}$. Let $𝐕=\{v_{ij}\}$ for $1\le i\le d$ and $1\le j\le k(r+1)$. Consider the following polynomial conditions.

The condition $Q_{i,j,h}^O(𝐕)=0$ requires the columns $i,j$ of $𝐕$ where to be pairwise orthogonal and the condition $Q_i^N(𝐕)=0$ requires the column $i$ to have length $1$. We will next show how a matrix $𝐕\in {ℝ}^{d\times k(r+1)}$ which satisfies all of the above conditions represents $k$-affine subspaces of dimension $r$. For $h\in [0,k-1]$ the columns $hr+1$ to $(h+1)r$ represent the orthonormal basis of the linear subspace corresponding to the $h$^th affine subspace of rank $r$ and column $(kr+h+1)$ represents the corresponding offset point. We combine all of the above equations into a single one by taking the sum of squares

Note that $Q(𝐕)=0$ if and only if $Q_{i,j,h}^O(𝐕)=0$ for all $h,i,j$ and $Q_i^N(𝐕)=0$ for all $i$. Consider the algebraic set $W\subseteq {ℝ}^{d\times k(r+1)}$ of all matrices satisfying Equation 1. We view each element of $W$ as a representation of $k$ affine subspaces of dimension $r$. Let $co{l}_1,co{l}_2,\mathrm{\dots }co{l}_{d\times k(r+1)}$ be the columns of an element $𝐕\in W$. Then, the $h$^th affine subspace is represented by the linear subspace spanned by the columns $co{l}_{hr+1}$ to $co{l}_{(h+1)r+1}$ and the point corresponding to the column $co{l}_{kr+h+1}$. Let ${𝐁}_{𝐡}$ denote the submatrix formed by columns $co{l}_{hr+1}$ to $co{l}_{(h+1)r+1}$. The squared distance from a point $𝐲\in {ℝ}^d$ to an $r$-dimensional affine subspace $𝐩+𝐁x$ is given by ${\Vert 𝐲-𝐩-{\mathrm{𝐁𝐁}}^T𝐲\Vert }_F$.

Now consider the family of polynomials defined over $W$ by

The polynomial $P_{i,j,f}(𝐕)>0$ if the $j$^th affine space represented by $𝐕$ is closer to ${𝐱}_f$ than the $i$^th affine space represented by $𝐕$ and vice-versa. For any particular $𝐕\in W$, the sign condition with respect to $𝒫$ gives an ordering of the affine subspaces with respect to the Euclidean distance from each of the input points. Hence, we can partition the $n$ input points based on the nearest affine subspace. Let $𝒞$ be the partition of $W$ on cells over $𝒫$. For each cell $C$, the sign condition with respect to $𝒫$ is constant over $C$, which implies that the partitioning of the input points is the same over all points in $C$. Also, let $A_1,A_2,\mathrm{\dots }{A}_k$ be an optimal solution for Projective Clustering. We can represent $A_i$ by ${𝐩}_{𝐢}$ and ${𝐁}_{𝐢}$ where ${𝐁}_{𝐢}\in {ℝ}^{d\times r}$ and the columns of ${𝐁}_{𝐢}$ are orthonormal. Here, ${𝐩}_{𝐢}$ is the offset point and ${𝐁}_{𝐢}$ is the $r$-dimensional linear subspace. Hence, there exists $𝐕\in W$ that represents $A_1,A_2,\mathrm{\dots }{A}_k$. Thus if we run the classic PCA algorithm for each partition generated by every non-empty cell $C$, we will find an optimal solution. Thus our algorithm proceeds as follows:

• $\mathrm{■}$

  Use the algorithm from Proposition 6 to obtain a point ${𝐕}_{𝐂}$ from each cell $C$ of the algebraic set $W$ over the family of polynomials $𝒫$.

• $\mathrm{■}$

  Run the PCA algorithm for each of the $k$ clusters generated by ${𝐕}_{𝐂}$ to get $k$ affine subspaces.

• $\mathrm{■}$

  Return the $k$-affine subspaces that minimize the sum of squares of distances.

The degree of $Q$ and polynomials from $𝒫$ is at most $4$, $|𝒫|=n{k}^2$, and the real dimension of $W$ is at most $dk(r+1)$ which is the dimension of ${ℝ}^{d\times k(r+1)}\supseteq W$. The algorithm from Proposition 6 does at most $t={(n{k}^2)}^{dk(r+1)}{2}^{𝒪(dk(r+1))}$ operations and produces at most $t$ points. Our algorithm runs $k$ instances of PCA for each such point and hence we have reduced our problem to solving $k{(n{k}^2)}^{dk(r+1)}{2}^{𝒪(dk(r+1))}=n^{𝒪(dk(r+1))}$ instances of PCA. Since PCA can be solved in polynomial time the overall running time of our algorithm is in $n^{𝒪(dk(r+1))}$.

We can reduce the problem to solving $k{(n{k}^2)}^{dk(d-r+1)}{2}^{𝒪(dk(dr+1))}=n^{𝒪(dk(d-r+1))}$ instances of PCA using a slightly different characterization of the $k$ $r$-dimensional affine subspaces. Note that every $r$-dimensional affine subspace of a $d$-dimensional Euclidean space ${ℝ}^d$ is defined by $y=𝐩+𝐕x$, where $𝐩$ is a point in ${ℝ}^d$ and $𝐕\in {ℝ}^{d\times r}$ represents the orthonormal basis of an $r$-dimensional linear subspace of ${ℝ}^d$. Let ${𝐕}^{𝐂}\in {ℝ}^{d\times (d-r)}$ be the orthogonal complement of $𝐕$. Thus for every $r$-dimensional affine subspace $A$ defined by $y=𝐩+𝐕x$, we have the corresponding unique affine subspace $\mathrm{𝖼𝗈𝗆𝗉}(A)$ defined by $y=𝐩+{𝐕}^{𝐂}x$. The points in the algebraic set will now represent $\mathrm{𝖼𝗈𝗆𝗉}(A)$ instead of the affine subspace $A$.

To this end, we consider the matrix space ${ℝ}^{d\times k(d-r+1)}$ and a matrix ${𝐕}^{𝐂}\in {ℝ}^{d\times k(d-r+1)}$. Let ${𝐕}^{𝐂}={\{v_{ij}\}}_{i,j}$ and consider the following polynomial conditions:

As above, we combine all equations into the following equivalent one:

Again, let $\tilde{W}\subseteq {ℝ}^{d\times k(d-r+1)}$ be the algebraic set of all matrices satisfying the above equation. We view each element of $\tilde{W}$ as a representation of $k$ affine subspaces of dimension $d-r$. For every element ${𝐕}^{𝐂}\in \tilde{W}$ and for each $h\in [0,k-1]$, the columns $h(d-r)+1$ to $(h+1)(d-r)$ represents the basis of the linear subspace corresponding to the $h$^th affine subspace of rank $d-r$ and column $k(d-r)+h+1$ represents the corresponding offset point. Let $co{l}_1,co{l}_2,\mathrm{\dots }co{l}_{d\times k(d-r+1)}$ be the columns of an element ${𝐕}^{𝐂}\in \tilde{W}$. The $h$^th affine subspace is represented by the linear subspace spanned by the columns $co{l}_{h(d-r)+1}$ to $co{l}_{(h+1)(d-r)+1}$ and the point corresponding to column $co{l}_{k(d-r)+h+1}$. We again denote the corresponding submatrix by ${𝐁}_{𝐡}$. The square of the distance from a point $𝐲\in {ℝ}^d$ to the orthogonal complement of an $(d-r)$-dimensional affine subspace defined by $𝐩+{𝐕}^{𝐂}x$ is given by ${\sum }_{i=1}^{d-r}{(v_i(𝐲-𝐩))}^2={\Vert {𝐕}^{𝐂}(𝐲-𝐩)\Vert }^2$. Now we define the family of polynomials over $W$ as

Note that ${\tilde{P}}_{i,j,f}({𝐕}^{𝐂})>0$ corresponds to the case that the $j$^th $r$-dimensional affine subspace represented by ${({𝐕}^{𝐂})}^{𝐂}=𝐕$ is closer to ${𝐱}_f$ than the $i$^th $r$-dimensional affine subspace represented by $𝐕$. By the same argument as above, we can iterate over all non-empty cells of sign conditions and for each cell, we compute a solution by solving $k$ instances of PCA. The degree of $\tilde{Q}$ and polynomials from $\widetilde{𝒫}$ is at most $4$, $|\widetilde{𝒫}|=n{k}^2$ and the real dimension of $W$ is at most $dk(d-r+1)$ which is the dimension of ${ℝ}^{d\times k(d-r+1)}\supseteq W$. The algorithm from Proposition 6 does at most $t={(n{k}^2)}^{dk(d-r+1)}{2}^{𝒪(dk(r+1))}$ operations and produces at most $t$ points. Our algorithm runs $k$ instances of PCA for each such point and hence we have reduced our problem to $k{(n{k}^2)}^{dk(d-r+1)}{2}^{𝒪(dk(r+1))}=n^{𝒪(dk(d-r+1))}$ instances of PCA. The overall running time in this case is $n^{𝒪(dk(d-r+1))}$. As we can choose the most efficient way to represent the affine subspace the running time of our algorithm is in $n^{𝒪(min\{dk(r+1),dk(d-r+1)\})}$. $◀$