Harm Derksen
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
Research Subjects
Harm Derksen has a total of 59 co-authors. Here are the top co-authors by number of shared publications:
- Gregor Kemper
University of Heidelberg
7 shared publications - Jerzy Weyman
Department of Mathematics, Northeastern University, Boston, Massachusetts 02115
6 shared publications - Visu Makam
Department of Mathematics, University of Michigan, Ann Arbor, MI, USA
5 shared publications - Arno van Den Essen
Dept. of Mathematics, Univ. of Nijmegen, 6525 ED Nijmegen, The Netherlands
4 shared publications - Kayvan Najarian
Gilbert S. Omenn Department of Computational Medicine and Bioinformatics, University of Michigan, Ann Arbor, USA
4 shared publications - Andrei Zelevinsky
Northeastern University
3 shared publications
Latest Publications
- Open Access
Invariants of finite groups acting on (free) skew fields
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 AccessInvariants of finite groups acting on (free) skew fields
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
- 24 November 2024
- Published by Springer Nature in Discover Artificial Intelligence
- Vol. 4 (1) , 1-8
Identifying selective PDHK inhibitors using coupled tensor matrix completion and experimental validation
- 24 November 2024
- Published by Springer Nature in Discover Artificial Intelligence
- Vol. 4 (1) , 1-8
Open AccessIdentifying selective PDHK inhibitors using coupled tensor matrix completion and experimental validation
- Open Access
Boosting uniformity in quasirandom groups: fast and simple
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 AccessBoosting uniformity in quasirandom groups: fast and simple
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
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 AccessBi-Lipschitz Quotient embedding for Euclidean Group actions on Data
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
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 AccessPseudorandomness, symmetry, smoothing: II
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
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 AccessPseudorandomness, symmetry, smoothing: I
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
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 AccessThe capacity of quiver representations and the Anantharam-Jog-Nair inequality
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
- 11 February 2023
- Published by MDPI AG in Algorithms
- Vol. 16 (2) , 104
Quadratic Multilinear Discriminant Analysis for Tensorial Data Classification
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 on clean signals—where the second best method reached —and an AUC of after adding noise to the signals (with a signal-to-noise-ratio of )—where the second best method reached . 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.- 11 February 2023
- Published by MDPI AG in Algorithms
- Vol. 16 (2) , 104
Open AccessQuadratic Multilinear Discriminant Analysis for Tensorial Data Classification
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 on clean signals—where the second best method reached —and an AUC of after adding noise to the signals (with a signal-to-noise-ratio of )—where the second best method reached . 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. - 1 February 2023
- Published by American Institute of Aeronautics and Astronautics (AIAA) in Journal of Guidance, Control, and Dynamics
- Vol. 46 (2) , 277-285
View Invariants for Three-Dimensional Points with Constrained Observer Motion
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.
- 1 February 2023
- Published by American Institute of Aeronautics and Astronautics (AIAA) in Journal of Guidance, Control, and Dynamics
- Vol. 46 (2) , 277-285
View Invariants for Three-Dimensional Points with Constrained Observer Motion
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
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.Open AccessRanks of linear matrix pencils separate simultaneous similarity orbits
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.