Pith. sign in

REVIEW 2 major objections 4 minor 66 references

$k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves that the k-subspace median—the subspace minimizing the sum of ordinary, non-squared Euclidean distances—admits a deterministic polynomial-time sqrt(d)-approximation, for every k up to d−1.

desk verdict The relaxation idea is real and the sqrt(d) proof is structurally sound, but the main theorem is not proven as stated because the solver is only epsilon-approximate and the t0 initial-point bound in Lemma 7.3 is false. read the letter →

arxiv 2507.14631 v1 pith:PJ7MVG3W submitted 2025-07-19 cs.LG cs.CGcs.DS

Daniel Greenhut , Dan Feldman This is my paper · ORCID
classification cs.LGcs.CGcs.DS MSC 68W2590C2290C25
keywords k-subspacemedianmixednormℓ_{21}semidefiniteprogrammingsecond-orderconedeterministicapproximationalgorithmprojectionmatrixroundingrobustsubspacenon-squaredEuclideandistances
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to solve the k-subspace median problem: given n points in R^d and an integer k, find the k-dimensional subspace that minimizes the sum of ordinary (non-squared) Euclidean distances to the points. This is a non-convex problem for k < d−1, and previous provable algorithms were randomized with running time or approximation factor exponential in k. The paper claims the first deterministic polynomial-time algorithm for the problem, with approximation factor $\sqrt$(d) and running time (nd log Δ)^{O(1)} for points with coordinates bounded by Δ. A sympathetic reader should care because the median subspace is more resistant to outliers than PCA, and a polynomial-time guarantee independent of k opens the door to large-k and high-dimensional applications.

What carries the argument

The load-bearing object is the mixed SDP-SOCP relaxation (Problem 6): a convex program whose feasible set is the convex hull of rank-(d−k) projection matrices, combining a positive-semidefinite constraint on X with second-order cone constraints ||X p_i||_2 ≤ y_i. The rounding step uses the vector q ∈ R^d of summed absolute projections onto the eigenaxes of the relaxed solution; choosing the d−k smallest entries of q is exactly a linear-programming min over binary vectors with that many ones (Proposition 6.1). The chain of inequalities ||diag(ζ) V p_i||_2 ≤ ||diag(ζ) V p_i||_1 ≤ ... ≤ $\sqrt$(d) ||X^* p_i||_2 connects the rounded projection to the relaxation optimum and yields the $\sqrt$(d) factor.

What would settle it

Take d=2, k=1, and a single input point p_1 = 100 e_1. With X_0 = (d−k)/d · I = I/2, compute t_0 = 2n / sum_i $\sqrt$(||X_0 p_i||^2 + e) = 2 / $\sqrt$(2500 + e) ≈ 0.04 < 1. Lemma 7.3 divides by t_0−1, so this input directly tests whether the claimed iteration bound covers all allowed inputs; observing the algorithm's termination time on such an input would settle whether Theorem 7.4 holds as stated.

Watch

Extended reading notes

Core claim

The central discovery is that the non-convex k-subspace median can be approximated by a convex relaxation over symmetric matrices: minimize the sum of auxiliary variables y_i subject to 0 ⪯ X ⪯ I, trace(X) = d−k, and ||X p_i||_2 ≤ y_i for every point. The minimizer X* is not itself a projection matrix, but the paper shows how to round it: diagonalize X*, compute q_j = sum_i |(V^T p_i)_j| for each eigenaxis, keep the d−k axes with smallest total absolute projection, and take the resulting projection matrix. This rounding yields a genuine k-subspace whose sum of non-squared distances is at most $\sqrt$(d) times the optimum, and the relaxation is solvable in polynomial time by a central-path interior-point method. Theorem 6.2 proves the approximation guarantee and Corollary 7.4.1 states the full polynomial running time.

Load-bearing premise

The polynomial-time part of the proof assumes that the initial-point parameter t0 defined in Lemma 7.3 is always larger than 1, because the argument divides by t0−1; for inputs with large coordinates t0 can be smaller than 1, so the stated bound on the number of interior-point iterations is not derived.

Editorial extensions

If this is right

  • For every point set with coordinates in [−Δ,Δ]^d and every k ∈ [1,d−1], the algorithm returns a k-subspace S with sum_i dist(p_i,S) ≤ sqrt(d) · ksm(P,k), in (nd log Δ)^{O(1)} time.
  • This settles, affirmatively, the open question of whether a deterministic polynomial-time approximation with a factor not exponential in k exists for the k-subspace median.
  • The same algorithm can be run on coresets or sketches of the input to obtain near-linear time in n, at the price of randomization, while keeping the approximation factor.
  • The techniques are expected to extend to other mixed ℓ_{2,z} objectives, such as the k-subspace center (z=∞), and to settings with outliers and sparsity demands.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the approximation factor depends only on d and not on k, the guarantee stays sqrt(d) even when k is Ω(d); for very high-dimensional inputs, composing the method with a dimension-reduction step would trade this factor for one that grows with k instead.
  • The rounding rule suggests a deterministic selection principle in the eigenbasis of the relaxed solution: pick the axes with smallest total absolute projection. This principle could be tested as a standalone heuristic on noisy datasets without solving the full SDP to high precision.
  • An immediate empirical check is whether, on datasets with outliers, the returned subspace achieves lower sum-of-distances loss than PCA/SVD, matching the comparison reported in the paper's experiments.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. This paper studies the k-subspace median (kSM) problem, minimizing the sum of Euclidean distances from n points to a k-dimensional linear subspace. The authors relax the non-convex rank-constrained problem (5) to a convex SDP-SOCP problem (6), solve the relaxation, and round the resulting PSD matrix via an eigendecomposition followed by a simple LP-based selection of d-k coordinates (Proposition 6.1). Theorem 6.2 proves, conditionally on computing an exact minimizer of the relaxation, that the rounding yields a sqrt(d)-approximation to kSM. Section 7 proposes a central-path method and claims polynomial running time, leading to Corollary 7.4.1. The paper also includes open-source code and experiments on two UCI datasets.

Significance. If the main result were fully established, it would be a significant advance: a deterministic polynomial-time approximation for kSM with approximation factor sqrt(d) and running time not exponential in k, answering an open problem stated in the paper. The relaxation-rounding idea is elegant, the inequality relaxksm(P,k) <= ksm(P,k) in (20) is correct by feasibility, and Theorem 6.2's proof is structurally sound under the exact-minimizer assumption. The paper also ships open code and reports experiments. However, the gap between the exact minimizer assumed in the correctness proof and the epsilon-approximate solver supplied in Section 7 is load-bearing, and the runtime analysis in Lemma 7.3 contains an invalid inequality; the advertised result is therefore not established in the present form.

major comments (2)
  1. [Sec. 7, Algorithm 1, Corollary 7.4.1] The algorithm's own solver does not certify the asserted multiplicative guarantee. Theorem 6.2 uses Eq. (26), which requires that (X*, y*) in Algorithm 1, Line 1 is an exact minimizer of Problem (6). Proposition 7.2 only produces a feasible (X~, y~) with 1^T y~ <= relaxksm(P,k) + epsilon. Repeating the proof with X~ gives sum_i dist(p_i,S) <= sqrt(d) * 1^T y~ <= sqrt(d)(relaxksm(P,k)+epsilon) <= sqrt(d)*ksm(P,k)+sqrt(d)*epsilon. For inputs with ksm(P,k)=0, e.g., P={(1,0),(2,0)} in R^2 with k=1, this bound is sqrt(2)*epsilon > 0, so the output is not certified to be a sqrt(d)-approximation under the paper's own definition in Section 4. Corollary 7.4.1 does not specify how epsilon should be chosen or how the additive term is absorbed, and Theorem 7.4's displayed time bound in (51) omits epsilon altogether. This is a gap in the central claim, not a local typo.
  2. [Lemma 7.3, Eqs. (34)-(50)] The bound t0 >= 2/sqrt(e) has the wrong direction. Since y0_i = sqrt(||X0 p_i||^2 + e) >= sqrt(e), the denominator of (34) is at least n*sqrt(e), so t0 <= 2/sqrt(e) ~ 1.21, and for large coordinates t0 can be much smaller than 1 (e.g., d=2, k=1, p_1=100 e_1 gives t0 ~ 0.04). The proof then divides by t0-1 in (50), which is invalid when t0 <= 1. Consequently the stated polynomial-time bound on the initial Newton iterations is not established. This does not affect the conditional sqrt(d) approximation proof, but it does affect the running-time half of the main theorem.
minor comments (4)
  1. [Theorem 6.2, Eq. (21)] In (21) the projection onto the output subspace is written as p_i - (I-E)V p_i, but the actual projection matrix defined in Line 10 is V(I-E)V^T. With V orthogonal the intended equality to ||E p_i||_2 becomes correct after replacing (I-E)V by V(I-E)V^T; the surrounding argument should be corrected accordingly.
  2. [Theorem 6.2, after Eq. (19)] The displayed chain 'sqrt(d) ||y||_1 <= ||y||_2 <= ||y||_1' is reversed; the correct statement is ||y||_2 <= ||y||_1 <= sqrt(d)||y||_2. The inequalities actually used in (17)-(19) are correct, so this is a presentation error.
  3. [Abstract and Section 4] The abstract speaks of approximating the 'affine k-subspace mean', but Problem (5) and the algorithm concern linear subspaces through the origin; the affine case needs the standard reduction mentioned in Section A. Please use the terminology consistently.
  4. [Algorithm 1, Line 1] The comment 'See Proposition 7.2 and Lemma 7.3' next to 'Compute a minimizer' is misleading because Proposition 7.2 only provides an epsilon-approximate solution. The pseudocode and the theorem statements should distinguish clearly between the exact minimizer used in Theorem 6.2 and the approximate solution used in the running-time section.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the sqrt(d)-approximation is derived from the relaxation's definition and standard inequalities, not from fitted parameters or self-citation.

full rationale

The paper's derivation is self-contained and not circular. The central guarantee is proved in Theorem 6.2 by a chain of inequalities: the rounding vector zeta is chosen by the linear program in Proposition 6.1 using q computed from the input projections; inequality (9) follows from feasibility of diag(D) in that LP; norm inequalities (17)-(19) are standard; and the key comparison relaxksm(P,k) <= ksm(P,k) at (20) follows by exhibiting any optimal (d-k)-projection matrix as a feasible point of the convex relaxation (6), not by assuming the conclusion. No parameter is fitted to the input in a way that forces the output cost, and no load-bearing step invokes the authors' own prior work: the convex relaxation and the rounding scheme are introduced and analyzed in this paper, while the cited central-path method [34] is an external textbook result. Two genuine issues appear in the manuscript -- the proof of Theorem 6.2 treats X* as an exact minimizer of (6) although Proposition 7.2 only supplies an additive epsilon-approximation, and Lemma 7.3 assumes t0 > 1 without justification -- but these are correctness and running-time gaps, not circularity, because the claimed approximation factor is compared against the true optimum rather than being defined in terms of the solver's epsilon. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central sqrt(d) approximation proof introduces no free parameters and no invented entities. The only load-bearing auxiliary input is the initial point construction in Lemma 7.3, whose proof contains the t0 > 1 error.

assumptions (3)
  • standard math The standard machinery of linear programming, self-concordant barriers, and the central path method applies to the mixed SDP-SOCP formulation.
    Invoked in Proposition 6.1, Lemma 7.1, Proposition 7.2, and Section D; these are classical results, not new to the paper.
  • domain assumption The input points lie in R^d with entries bounded in absolute value by Δ, and n ≥ d.
    Assumed at the start of Section 4 and used in Theorem 7.4 for the bit-size dependence of the runtime.
  • ad hoc to paper A strictly feasible starting point for the conic problem can be computed and the central path initialized with a polynomially bounded gap ρ.
    Lemma 7.3 attempts to prove this but relies on the false inequality t0 > 1; this is the gap in the runtime proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of $k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation." pith.science (2026). https://pith.science/paper/PJ7MVG3W

@misc{pith2026250714631,
  author       = {Pith},
  title        = {Pith review of: $k$-PCA for (non-squared) Euclidean Distances: Polynomial Time Approximation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PJ7MVG3W}},
  note         = {Machine review of arXiv:2507.14631}
}
abstract

Given an integer $k\geq1$ and a set $P$ of $n$ points in $\REAL^d$, the classic $k$-PCA (Principle Component Analysis) approximates the affine \emph{$k$-subspace mean} of $P$, which is the $k$-dimensional affine linear subspace that minimizes its sum of squared Euclidean distances ($\ell_{2,2}$-norm) over the points of $P$, i.e., the mean of these distances. The \emph{$k$-subspace median} is the subspace that minimizes its sum of (non-squared) Euclidean distances ($\ell_{2,1}$-mixed norm), i.e., their median. The median subspace is usually more sparse and robust to noise/outliers than the mean, but also much harder to approximate since, unlike the $\ell_{z,z}$ (non-mixed) norms, it is non-convex for $k<d-1$. We provide the first polynomial-time deterministic algorithm whose both running time and approximation factor are not exponential in $k$. More precisely, the multiplicative approximation factor is $\sqrt{d}$, and the running time is polynomial in the size of the input. We expect that our technique would be useful for many other related problems, such as $\ell_{2,z}$ norm of distances for $z\not \in \br{1,2}$, e.g., $z=\infty$, and handling outliers/sparsity. Open code and experimental results on real-world datasets are also provided.

Figures

Figures reproduced from arXiv: 2507.14631 by the authors.

Figure 1
Figure 1. An illustration of the search space in Algorithm 1 for the case d = 2 and k = 1 (line-median in the plane). Every point is a matrix in R 2×2 . The gray ellipsoid consists of S + 2 ⊆ R 2×2 which is the search space of Problem 6, and its (non-convex) boundary consists of those matrices whose rank is d − k = 1 (projection matrices) which is the search space of the original kSM problem (5). The values of the function of… view at source ↗
Figure 2
Figure 2. Comparison of Algorithm 1 with SVD and the method by Shyamalkumar and Varadarajan on UC Irvine datasets. Figures 2a and 2c: Log of the sum of distances from the data points to the subspace. Figures 2b and 2d: Computation time in microseconds, shown with Japanese candlesticks and a batch size of 3. We conducted experiments of dimensional reduction on two UC Irvine datasets: ”Statlog (Vehicle Sil￾houettes)” [37] (n = … view at source ↗
Figure 3
Figure 3. Logarithmic running time of Algorithm 1 on ’Statlog (Vehicle Silhouettes)’ as the number of points increase (fixed d = 19, k = 9). The Japanese candlesticks are for 20-point batches. To validate the results we obtained in Section 7, we analyzed the runtime of the ”Statlog (Vehicle Silhouettes)” dataset as the number of points varied, with d = 19 and k = 9 fixed [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

66 extracted references · 61 canonical work pages

  1. [1]

    A robust autoregressive gaussian process motion model usingl1-norm based low-rank kernel matrix approximation,

    E. Kim, S. Choi, and S. Oh, “A robust autoregressive gaussian process motion model usingl1-norm based low-rank kernel matrix approximation,” in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems , pp. 4396–4401, IEEE, 2014

    work page 2014

  2. [2]

    Linear-time estimation with tree assumed density filtering and low-rank ap- proximation,

    D.-N. Ta and F. Dellaert, “Linear-time estimation with tree assumed density filtering and low-rank ap- proximation,” in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4556– 4563, IEEE, 2014

    work page 2014

  3. [3]

    A comparative study on PCA and LDA based EMG pattern recognition for anthropomorphic robotic hand,

    D. Zhang, X. Zhao, J. Han, and Y. Zhao, “A comparative study on PCA and LDA based EMG pattern recognition for anthropomorphic robotic hand,” in 2014 IEEE International Conference on Robotics and Automation (ICRA) , pp. 4850–4855, IEEE, 2014

    work page 2014

  4. [4]

    Real-time scalable 6dof pose estimation for textureless objects,

    Z. Cao, Y. Sheikh, and N. K. Banerjee, “Real-time scalable 6dof pose estimation for textureless objects,” in 2016 IEEE International conference on Robotics and Automation (ICRA), pp. 2441–2448, IEEE, 2016

    work page 2016

  5. [5]

    Self-localization from images with small overlap,

    T. Kanji, “Self-localization from images with small overlap,” in 2016 IEEE/RSJ International Confer- ence on Intelligent Robots and Systems (IROS) , pp. 4497–4504, IEEE, 2016

    work page 2016

  6. [6]

    Smart-inspect: micro scale localization and classification of smartphone glass defects for industrial automation,

    M. U. M. Bhutta, S. Aslam, P. Yun, J. Jiao, and M. Liu, “Smart-inspect: micro scale localization and classification of smartphone glass defects for industrial automation,” in 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) , pp. 2860–2865, IEEE, 2020

    work page 2020

  7. [7]

    Self-supervised weed detection in vegetable crops using ground based hyperspectral imaging,

    A. Wendel and J. Underwood, “Self-supervised weed detection in vegetable crops using ground based hyperspectral imaging,” in 2016 IEEE international conference on robotics and automation (ICRA) , pp. 5128–5135, IEEE, 2016

    work page 2016

  8. [8]

    Low rank approximation with entrywise l1-norm error,

    Z. Song, D. P. Woodruff, and P. Zhong, “Low rank approximation with entrywise l1-norm error,” in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing , pp. 688–701, 2017

    work page 2017

Show all 66 references
  1. [9]

    Tight bounds for sketching the operator norm, schatten norms, and sub- space embeddings,

    Y. Li and D. P. Woodruff, “Tight bounds for sketching the operator norm, schatten norms, and sub- space embeddings,” in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) , pp. 39–1, 2016

    2016

  2. [10]

    Sampling algorithms and coresets for lp regression,

    A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney, “Sampling algorithms and coresets for lp regression,” SIAM Journal on Computing , vol. 38, no. 5, pp. 2060–2078, 2009

    2009

  3. [11]

    Coresets forweighted facilities and their applications,

    D. Feldman, A. Fiat, and M. Sharir, “Coresets forweighted facilities and their applications,” in 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06) , pp. 315–324, IEEE, 2006

    2006

  4. [12]

    Coresets for near-convex functions,

    M. Tukan, A. Maalouf, and D. Feldman, “Coresets for near-convex functions,” Advances in Neural Information Processing Systems, vol. 33, pp. 997–1009, 2020

    2020

  5. [13]

    Tight sensitivity bounds for smaller coresets,

    A. Maalouf, A. Statman, and D. Feldman, “Tight sensitivity bounds for smaller coresets,” in Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining , pp. 2051– 2061, 2020

    2020

  6. [14]

    Recent advances in continuous location theory,

    P. Hansen and J.-F. Thisse, “Recent advances in continuous location theory,” Sistemi Urbani , vol. 1, pp. 33–54, 1983

    1983

  7. [15]

    Euclidean constructibility in graph-minimization problems,

    E. J. Cockayne and Z. A. Melzak, “Euclidean constructibility in graph-minimization problems,” Math- ematics Magazine , vol. 42, no. 4, pp. 206–208, 1969

    1969

  8. [16]

    Geometric median in nearly linear time,

    M. B. Cohen, Y. T. Lee, G. Miller, J. Pachocki, and A. Sidford, “Geometric median in nearly linear time,” in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing , pp. 9–21, 2016

    2016

  9. [17]

    Efficient subspace approximation algorithms,

    N. D. Shyamalkumar and K. Varadarajan, “Efficient subspace approximation algorithms,” in SODA, vol. 7, pp. 532–540, 2007

    2007

  10. [18]

    Success amplification and random sampling,

    J. Hromkovi ˇC, “Success amplification and random sampling,” in Design and Analysis of Randomized Algorithms, pp. 153–182, Springer, 2005

    2005

  11. [19]

    Sampling-based dimension reduction for subspace approximation,

    A. Deshpande and K. Varadarajan, “Sampling-based dimension reduction for subspace approximation,” in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing , pp. 641–650, 2007

    2007

  12. [20]

    Coresets and sketches for high di- mensional subspace approximation problems,

    D. Feldman, M. Monemizadeh, C. Sohler, and D. P. Woodruff, “Coresets and sketches for high di- mensional subspace approximation problems,” in Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms , pp. 630–649, SIAM, 2010

    2010

  13. [21]

    Input sparsity and hardness for robust subspace approximation,

    K. L. Clarkson and D. P. Woodruff, “Input sparsity and hardness for robust subspace approximation,” in 2015 IEEE 56th annual symposium on foundations of computer science , pp. 310–329, IEEE, 2015

    2015

  14. [22]

    Optimal algorithms for l1-subspace signal processing,

    P. P. Markopoulos, G. N. Karystinos, and D. A. Pados, “Optimal algorithms for l1-subspace signal processing,” IEEE Transactions on Signal Processing , vol. 62, no. 19, pp. 5046–5058, 2014

    2014

  15. [23]

    Algorithms for ℓ p low-rank approximation,

    F. Chierichetti, S. Gollapudi, R. Kumar, S. Lattanzi, R. Panigrahy, and D. P. Woodruff, “Algorithms for ℓ p low-rank approximation,” in International Conference on Machine Learning , pp. 806–814, PMLR, 2017

    2017

  16. [24]

    Low-rank approximation with 1/ϵ 1/3 matrix-vector products,

    A. Bakshi, K. L. Clarkson, and D. P. Woodruff, “Low-rank approximation with 1/ϵ 1/3 matrix-vector products,” in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pp. 1130–1143, 2022

    2022

  17. [25]

    Generalized s-numbers of τ -measurable operators,

    T. Fack and H. Kosaki, “Generalized s-numbers of τ -measurable operators,” Pacific Journal of Mathe- matics, vol. 123, no. 2, pp. 269–300, 1986

    1986

  18. [26]

    Efficient l1-norm principal-component analysis via bit flipping,

    P. P. Markopoulos, S. Kundu, S. Chamadia, and D. A. Pados, “Efficient l1-norm principal-component analysis via bit flipping,” IEEE Transactions on Signal Processing, vol. 65, no. 16, pp. 4252–4264, 2017

    2017

  19. [27]

    L1-PCA Toolbox

    P. Markopoulos, “L1-PCA Toolbox.” https://www.mathworks.com/matlabcentral/fileexchange/ 64855-l1-pca-toolbox , 2025. MATLAB Central File Exchange. Retrieved July 14, 2025

    2025

  20. [28]

    Greenhut and T

    D. Greenhut and T. Polinsky, “KSM.” https://github.com/danielgre134/KSM, 2022

    2022

  21. [29]

    On least squares solutions subject to a rank restriction,

    H. Wang, “On least squares solutions subject to a rank restriction,” Linear and Multilinear Algebra , vol. 63, no. 2, pp. 264–273, 2015

    2015

  22. [30]

    The monotonicity theorem, cauchy’s interlace theorem, and the courant-fischer theorem,

    Y. Ikebe, T. Inagaki, and S. Miyamoto, “The monotonicity theorem, cauchy’s interlace theorem, and the courant-fischer theorem,” The American Mathematical Monthly , vol. 94, no. 4, pp. 352–354, 1987

    1987

  23. [31]

    S. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization . Cambridge university press, 2004

    2004

  24. [32]

    Matrix computations, johns hopkins u,

    G. H. Golub and C. F. Van Loan, “Matrix computations, johns hopkins u,” Math. Sci., Johns Hopkins University Press, Baltimore, MD , 1996

    1996

  25. [33]

    The fundamental theorem of linear programming: extensions and applications,

    F. Tardella, “The fundamental theorem of linear programming: extensions and applications,” Optimiza- tion, vol. 60, no. 1-2, pp. 283–301, 2011

    2011

  26. [34]

    Interior point polynomial methods in convex programming,

    Y. Nesterov, “Interior point polynomial methods in convex programming,” Theory and Applications , 1994

    1994

  27. [35]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski, Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001

    2001

  28. [36]

    Beck, First-order methods in optimization

    A. Beck, First-order methods in optimization . SIAM, 2017

    2017

  29. [37]

    Statlog (Vehicle Silhouettes)

    P. Mowforth and B. Shepherd, “Statlog (Vehicle Silhouettes).” UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C5HG6N

    doi

  30. [38]

    Optical Recognition of Handwritten Digits

    E. Alpaydin and C. Kaynak, “Optical Recognition of Handwritten Digits.” UCI Machine Learning Repository, 1998. DOI: https://doi.org/10.24432/C50P49

    1998 doi

  31. [39]

    Vehicle recognition using rule based methods,

    J. P. Siebert, “Vehicle recognition using rule based methods,” 1987

    1987

  32. [40]

    Methods of combining multiple classifiers and their application to handwritten digit recog- nition,

    C. Kaynak, “Methods of combining multiple classifiers and their application to handwritten digit recog- nition,” Master’s thesis, Fen Bilimleri Enstit¨ us¨ u, 1995

    1995

  33. [41]

    L1-Norm-Algorithms

    ktountas, “L1-Norm-Algorithms.” https://github.com/ktountas/L1-Norm-Algorithms.git, 2021

    2021

  34. [42]

    Breakdown points of affine equivariant estimators of multivariate location and covariance matrices,

    H. P. Lopuhaa and P. J. Rousseeuw, “Breakdown points of affine equivariant estimators of multivariate location and covariance matrices,” The Annals of Statistics , pp. 229–248, 1991

    1991

  35. [43]

    Liii. on lines and planes of closest fit to systems of points in space,

    K. Pearson, “Liii. on lines and planes of closest fit to systems of points in space,”The London, Edinburgh, and Dublin philosophical magazine and journal of science , vol. 2, no. 11, pp. 559–572, 1901

    1901

  36. [44]

    Some options for l1-subspace signal processing,

    P. P. Markopoulos, G. N. Karystinos, and D. A. Pados, “Some options for l1-subspace signal processing,” in ISWCS 2013; The Tenth International Symposium on Wireless Communication Systems , pp. 1–5, VDE, 2013

    2013

  37. [45]

    An independent benchmarking of sdp and socp solvers,

    H. D. Mittelmann, “An independent benchmarking of sdp and socp solvers,” Mathematical Program- ming, vol. 95, no. 2, pp. 407–430, 2003

    2003

  38. [46]

    Mixed sdp/socp moment relaxations of the optimal power flow problem,

    D. K. Molzahn and I. A. Hiskens, “Mixed sdp/socp moment relaxations of the optimal power flow problem,” in 2015 IEEE Eindhoven PowerTech , pp. 1–6, IEEE, 2015

    2015

  39. [47]

    R1-PAC: rotational invariantL1-norm principal component anal- ysis for robust subspace factorization,

    C. Ding, D. Zhou, X. He, and H. Zha, “ R1-PAC: rotational invariantL1-norm principal component anal- ysis for robust subspace factorization,” in Proceedings of the 23rd international conference on Machine learning, pp. 281–288, 2006

    2006

  40. [48]

    Bi-criteria linear-time approximations for general- ized k-mean/median/center,

    D. Feldman, A. Fiat, M. Sharir, and D. Segev, “Bi-criteria linear-time approximations for general- ized k-mean/median/center,” in Proceedings of the twenty-third annual symposium on Computational geometry, pp. 19–26, 2007

    2007

  41. [49]

    The abel–ruffini theorem: Complex but not complicated,

    P. Ramond, “The abel–ruffini theorem: Complex but not complicated,” The American Mathematical Monthly, vol. 129, no. 3, pp. 231–245, 2022

    2022

  42. [50]

    Improved approximation algorithms for large matrices via random projections,

    T. Sarlos, “Improved approximation algorithms for large matrices via random projections,” in 2006 47th annual IEEE symposium on foundations of computer science (FOCS’06) , pp. 143–152, IEEE, 2006

    2006

  43. [51]

    Low rank matrix approximation in linear time,

    S. Har-Peled, “Low rank matrix approximation in linear time,” arXiv preprint arXiv:1410.8802 , 2014

    2014 arXiv

  44. [52]

    Adaptive sampling and fast low-rank matrix approximation,

    A. Deshpande and S. Vempala, “Adaptive sampling and fast low-rank matrix approximation,” in International Workshop on Approximation Algorithms for Combinatorial Optimization , pp. 292–303, Springer, 2006

    2006

  45. [53]

    Matrix approximation and projective clustering via volume sampling,

    A. Deshpande, L. Rademacher, S. S. Vempala, and G. Wang, “Matrix approximation and projective clustering via volume sampling,” Theory of Computing , vol. 2, no. 1, pp. 225–247, 2006

    2006

  46. [54]

    Polynomial time algorithm for column-row based relative-error low-rank matrix approximation,

    P. Drineas, M. W. Mahoney, and S. Muthukrishnan, “Polynomial time algorithm for column-row based relative-error low-rank matrix approximation,” tech. rep., Technical report 2006-04, DIMACS, 2006

    2006

  47. [55]

    Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix,

    P. Drineas, R. Kannan, and M. W. Mahoney, “Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix,” SIAM Journal on computing , vol. 36, no. 1, pp. 158–183, 2006

    2006

  48. [56]

    The complexity of the matrix eigenproblem,

    V. Y. Pan and Z. Q. Chen, “The complexity of the matrix eigenproblem,” in Proceedings of the thirty- first annual ACM symposium on Theory of computing , pp. 507–516, 1999

    1999

  49. [57]

    Complexity of finding the eigendecomposition of a matrix

    L. Reyzin, “Complexity of finding the eigendecomposition of a matrix.” Computer Science Stack Ex- change, 2024

    2024

  50. [58]

    Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering,

    D. Feldman, M. Schmidt, and C. Sohler, “Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering,” SIAM Journal on Computing , vol. 49, no. 3, pp. 601–657, 2020

    2020

  51. [59]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver,Geometric algorithms and combinatorial optimization , vol. 2. Springer Science & Business Media, 2012

    2012

  52. [60]

    Mathematical problems for the next century,

    S. Smale, “Mathematical problems for the next century,” The mathematical intelligencer, vol. 20, no. 2, pp. 7–15, 1998

    1998

  53. [61]

    Approximating the radii of point sets,

    K. Varadarajan, S. Venkatesh, Y. Ye, and J. Zhang, “Approximating the radii of point sets,” SIAM Journal on Computing , vol. 36, no. 6, pp. 1764–1776, 2007

    2007

  54. [62]

    Algorithms and hardness for subspace approximation,

    A. Deshpande, M. Tulsiani, and N. K. Vishnoi, “Algorithms and hardness for subspace approximation,” in Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pp. 482–496, SIAM, 2011

    2011

  55. [63]

    New frameworks for offline and streaming coreset constructions,

    V. Braverman, D. Feldman, H. Lang, A. Statman, and S. Zhou, “New frameworks for offline and streaming coreset constructions,” arXiv preprint arXiv:1612.00889 , 2016

    2016 arXiv

  56. [64]

    Dimensionality reduction for the sum-of-distances metric,

    Z. Feng, P. Kacham, and D. Woodruff, “Dimensionality reduction for the sum-of-distances metric,” in International Conference on Machine Learning , pp. 3220–3229, PMLR, 2021

    2021

  57. [65]

    Strong coresets for k-median and subspace approximation: Goodbye dimension,

    C. Sohler and D. P. Woodruff, “Strong coresets for k-median and subspace approximation: Goodbye dimension,” in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) , pp. 802–813, IEEE, 2018

    2018

  58. [66]

    Improved coresets and sublinear algorithms for power means in Euclidean spaces,

    V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn, “Improved coresets and sublinear algorithms for power means in Euclidean spaces,” Advances in Neural Information Processing Systems , vol. 34, pp. 21085–21098, 2021

    2021

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.