HDHarm Derksen

Harm Derksen

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Harm Derksen has a total of 59 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Invariants of finite groups acting on (free) skew fields

    by Harm Derksen, Jurij Volčič

    Let $M$ be a finitely generated skew field over a ground field $k$, and let $G$ be a finite group of $k$-linear automorphisms of $M$. This paper investigates finite generation of the skew subfield $M^G$ of $G$-invariants in $M$, and relations between the generators. The first main result shows that $M^G$ is finitely generated. Stronger conclusions hold when $M$ is a free skew field, i.e., the universal skew field of fractions of a free algebra. The second main result is the solution of the free Noether problem for non-modular linear group actions: if $G$ acts linearly on the free skew field $M$ on $m$ generators and the characteristic of $k$ does not divide $|G|$, then $M^G$ is the free skew field on $|G|(m-1)+1$ generators. In contrast, a nonlinear action of $Z_2$ on the free skew field $M$ on two generators is presented such that $M^{Z_2}$ is not a free skew field, resolving the free Lüroth problem. This action also exposes a non-scalar element of $M$ whose centralizer is not a rational field, refuting a conjecture of P. M. Cohn from 1978.

  • Open Access

    Identifying selective PDHK inhibitors using coupled tensor matrix completion and experimental validation

    by Flora Rajaei, Peter Toogood, Renju Jacob, Mason Baber, Mya Gough, Harm Derksen, Emily Wittrup, Kayvan Najarian

  • Open Access

    Boosting uniformity in quasirandom groups: fast and simple

    by Harm Derksen, Chin Ho Lee, Emanuele Viola

    We study the communication complexity of multiplying $k\times t$ elements from the group $H=\text{SL}(2,q)$ in the number-on-forehead model with $k$ parties. We prove a lower bound of $(t\log H)/c^{k}$. This is an exponential improvement over previous work, and matches the state-of-the-art in the area. Relatedly, we show that the convolution of $k^{c}$ independent copies of a 3-uniform distribution over $H^{m}$ is close to a $k$-uniform distribution. This is again an exponential improvement over previous work which needed $c^{k}$ copies. The proofs are remarkably simple; the results extend to other quasirandom groups. We also show that for any group $H$, any distribution over $H^{m}$ whose weight-$k$ Fourier coefficients are small is close to a $k$-uniform distribution. This generalizes previous work in the abelian setting, and the proof is simpler.

  • Open Access

    Bi-Lipschitz Quotient embedding for Euclidean Group actions on Data

    by Harm Derksen

    For the action of the orthogonal group or euclidean group on k-tuples of vectors we construct a bi-Lipschitz embedding from the orbit space into euclidean space.This embedding has distortion sqrt(2).

  • Open Access

    Pseudorandomness, symmetry, smoothing: II

    by Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

    We prove several new results on the Hamming weight of bounded uniform and small-bias distributions. We exhibit bounded-uniform distributions whose weight is anti-concentrated, matching existing concentration inequalities. This construction relies on a recent result in approximation theory due to Erdéyi (Acta Arithmetica 2016). In particular, we match the classical tail bounds, generalizing a result by Bun and Steinke (RANDOM 2015). Also, we improve on a construction by Benjamini, Gurel-Gurevich, and Peled (2012). We give a generic transformation that converts any bounded uniform distribution to a small-bias distribution that almost preserves its weight distribution. Applying this transformation in conjunction with the above results and others, we construct small-bias distributions with various weight restrictions. In particular, we match the concentration that follows from that of bounded uniformity and the generic closeness of small-bias and bounded-uniform distributions, answering a question by Bun and Steinke (RANDOM 2015). Moreover, these distributions are supported on only a constant number of Hamming weights. We further extend the anti-concentration constructions to small-bias distributions perturbed with noise, a class that has received much attention recently in derandomization. Our results imply (but are not implied by) a recent result of the authors (CCC 2024), and are based on different techniques. In particular, we prove that the standard Gaussian distribution is far from any mixture of Gaussians with bounded variance.

  • Open Access

    Pseudorandomness, symmetry, smoothing: I

    by Harm Derksen, Peter Ivanov, Chin Ho Lee, Emanuele Viola

    We prove several new results about bounded uniform and small-bias distributions. A main message is that, small-bias, even perturbed with noise, does not fool several classes of tests better than bounded uniformity. We prove this for threshold tests, small-space algorithms, and small-depth circuits. In particular, we obtain small-bias distributions that 1) achieve an optimal lower bound on their statistical distance to any bounded-uniform distribution. This closes a line of research initiated by Alon, Goldreich, and Mansour in 2003, and improves on a result by O'Donnell and Zhao. 2) have heavier tail mass than the uniform distribution. This answers a question posed by several researchers including Bun and Steinke. 3) rule out a popular paradigm for constructing pseudorandom generators, originating in a 1989 work by Ajtai and Wigderson. This again answers a question raised by several researchers. For branching programs, our result matches a bound by Forbes and Kelley. Our small-bias distributions above are symmetric. We show that the xor of any two symmetric small-bias distributions fools any bounded function. Hence our examples cannot be extended to the xor of two small-bias distributions, another popular paradigm whose power remains unknown. We also generalize and simplify the proof of a result of Bazzi.

  • Open Access

    The capacity of quiver representations and the Anantharam-Jog-Nair inequality

    by Calin Chindris, Harm Derksen

    The Anantharam-Jog-Nair inequality [AJN22] in Information Theory provides a unifying approach to the information-theoretic form of the Brascamp-Lieb inequality [CCE09] and the Entropy Power inequality [ZF93]. In this paper, we use methods from Quiver Invariant Theory [CD21] to study Anantharam-Jog-Nair inequalities with integral exponents. For such an inequality, we first view its input datum as a quiver datum and show that the best constant that occurs in the Anantharam-Jog-Nair inequality is of the form $-{1\over 2}\log (\mathbf{cap}(V,σ))$ where $\mathbf{cap}(V, σ)$ is the capacity of a quiver datum $(V, σ)$ of a complete bipartite quiver. The general tools developed in [CD21], when applied to complete bipartite quivers, yield necessary and sufficient conditions for: (1) the finiteness of the Anantharam-Jog-Nair best constants; and (2) the existence of Gaussian extremizers. These results recover some of the main results in [AJN22] and [ACZ22]. In addition, we characterize gaussian-extremizable data in terms of semi-simple data, and provide a general character formula for the Anatharam-Jog-Nair constants. Furthermore, our quiver invariant theoretic methods lead to necessary and sufficient conditions for the uniqueness of Gaussian extremizers. This answers the third and last question left unanswered in [AJN22].

  • Open Access

    Quadratic Multilinear Discriminant Analysis for Tensorial Data Classification

    by Cristian Minoccheri, Olivia Alge, Jonathan Gryak, Kayvan Najarian, Harm Derksen

    Over the past decades, there has been an increase of attention to adapting machine learning methods to fully exploit the higher order structure of tensorial data. One problem of great interest is tensor classification, and in particular the extension of linear discriminant analysis to the multilinear setting. We propose a novel method for multilinear discriminant analysis that is radically different from the ones considered so far, and it is the first extension to tensors of quadratic discriminant analysis. Our proposed approach uses invariant theory to extend the nearest Mahalanobis distance classifier to the higher-order setting, and to formulate a well-behaved optimization problem. We extensively test our method on a variety of synthetic data, outperforming previously proposed MDA techniques. We also show how to leverage multi-lead ECG data by constructing tensors via taut string, and use our method to classify healthy signals versus unhealthy ones; our method outperforms state-of-the-art MDA methods, especially after adding significant levels of noise to the signals. Our approach reached an AUC of 0.95(0.03) on clean signals—where the second best method reached 0.91(0.03)—and an AUC of 0.89(0.03) after adding noise to the signals (with a signal-to-noise-ratio of −30)—where the second best method reached 0.85(0.05). Our approach is fundamentally different than previous work in this direction, and proves to be faster, more stable, and more accurate on the tests we performed.


  • View Invariants for Three-Dimensional Points with Constrained Observer Motion

    by Paul D. McKee, Harm Derksen, John A. Christian

    Images from cameras are a common source of navigation information for a variety of vehicles. Such navigation often requires the matching of observed objects (e.g., landmarks, beacons, stars) in an image to a catalog (or map) of known objects. In many cases, this matching problem is made easier through the use of invariants. However, if the objects are modeled as three-dimensional points in general position, it has long been known that there are no invariants for a camera that is also in general position. This work discusses how invariants are introduced when the camera’s motion is constrained to a line, and proves that this is the only camera path along which invariants are possible. Algorithms are presented for computing both the invariants and the location for a camera undergoing rectilinear motion. The applicability of these ideas is discussed within the context of trains, aircraft, and spacecraft.

  • Open Access

    Ranks of linear matrix pencils separate simultaneous similarity orbits

    by Harm Derksen, Igor Klep, Visu Makam, Jurij Volčič

    This paper solves the two-sided version and provides a counterexample to the general version of the 2003 conjecture by Hadwin and Larson. Consider evaluations of linear matrix pencils $L=T_0+x_1T_1+\cdots+x_mT_m$ on matrix tuples as $L(X_1,\dots,X_m)=I\otimes T_0+X_1\otimes T_1+\cdots+X_m\otimes T_m$. It is shown that ranks of linear matrix pencils constitute a collection of separating invariants for simultaneous similarity of matrix tuples. That is, $m$-tuples $A$ and $B$ of $n\times n$ matrices are simultaneously similar if and only if the ranks of $L(A)$ and $L(B)$ are equal for all linear matrix pencils $L$ of size $mn$. Variants of this property are also established for symplectic, orthogonal, unitary similarity, and for the left-right action of general linear groups. Furthermore, a polynomial time algorithm for orbit equivalence of matrix tuples under the left-right action of special linear groups is deduced.