Shmuel Friedland - University of Illinois at Chicago

Shmuel Friedland
Are you Shmuel Friedland?

Claim your profile, edit publications, add additional information:

Contact Details

Shmuel Friedland
University of Illinois at Chicago
United States

Pubs By Year

Pub Categories

Mathematics - Mathematical Physics (13)
Mathematical Physics (13)
Quantum Physics (11)
Mathematics - Combinatorics (9)
Mathematics - Algebraic Geometry (7)
Mathematics - Classical Analysis and ODEs (7)
Mathematics - Numerical Analysis (6)
Computer Science - Computational Complexity (6)
Computer Science - Discrete Mathematics (5)
Mathematics - Optimization and Control (5)
Mathematics - Functional Analysis (2)
Computer Science - Information Theory (2)
Mathematics - Information Theory (2)
Physics - Statistical Mechanics (1)
Mathematics - Spectral Theory (1)
Mathematics - History and Overview (1)
Mathematics - Dynamical Systems (1)
Computer Science - Data Structures and Algorithms (1)
Mathematics - Quantum Algebra (1)
Mathematics - Rings and Algebras (1)
Mathematics - Metric Geometry (1)
Computer Science - Computer Vision and Pattern Recognition (1)

Publications Authored By Shmuel Friedland

The geometric measure of entanglement $E$ of an $m$ qubit quantum state takes maximal possible value $m$. In previous work of Gross, Flammia, and Eisert, it was shown that $E \ge m-O(\log m)$ with high probability as $m\to\infty$. They showed, as a consequence, that the vast majority of states are too entangled to be computationally useful. Read More

In the first part of this paper we generalize the result of Georgiou-Pavon that a positive square matrix can be scaled uniquely to a column stochastic matrix which maps a given positive probability vector to another given positive probability vector. In the second part of this paper we prove that a positive quantum channel can be scaled to another positive quantum channel which maps a given positive definite density matrix to another given positive definite density matrix using Brower's fixed point theorem. This result proves the Georgiou-Pavon conjecture for two positive definite density matrices in their recent paper. Read More

We give a simple formula for finding the spectral norm of d-mode symmetric tensor in two variables over the complex or real numbers in terms of the complex or real roots of a corresponding polynomial in one complex variable. This result implies that the geometric measure of entanglement of symmetric d-qubits is polynomial-time computable. We discuss a generalization to d-mode symmetric tensor in more than two variables. Read More

It is well known that a best rank-$R$ approximation of order-3 tensors may not exist for $R\ge 2$. A best rank-$(R,R,R)$ approximation always exists, however, and is also a best rank-$R$ approximation when it has rank (at most) $R$. For $R=2$ and real order-3 tensors it is shown that a best rank-2 approximation is also a local minimum of the best rank-(2,2,2) approximation problem. Read More

We show that for any given norm ball or proper cone, weak membership in its dual ball or dual cone is polynomial-time reducible to weak membership in the given ball or cone. A consequence is that the weak membership or membership problem for a ball or cone is NP-hard if and only if the corresponding problem for the dual ball or cone is NP-hard. In a similar vein, we show that computation of the dual norm of a given norm is polynomial-time reducible to computation of the given norm. Read More

We give sufficient conditions on a symmetric tensor S in S^dF^n to satisfy the equality: the symmetric rank of S, denoted as srank(S), is equal to the rank of S, denoted as rank(S). This is done by considering the rank of the unfolded S viewed as a matrix A(S). The condition is: rank(S) is in {rank(A(S)),rank (A(S))+1}. Read More

In this paper, we consider the planted partition model, in which $n = ks$ vertices of a random graph are partitioned into $k$ "clusters," each of size $s$. Edges between vertices in the same cluster and different clusters are included with constant probability $p$ and $q$, respectively (where $0 \le q < p \le 1$). We give an efficient algorithm that, with high probability, recovers the clustering as long as the cluster sizes are are least $\Omega(\sqrt{n})$. Read More

In this paper we give necessary and sufficient conditions for the equality case in Wielandt's eigenvalue inequality. Read More

In this paper we deal with a best approximation of a vector with respect to a closed semi-algebraic set $C$ in the space $\mathbb{R}^n$ endowed with a semi-algebraic norm $\nu$. Under additional assumptions on $\nu$ we prove semi-algebraicity of the set of points of unique approximation and other sets associated with the distance to $C$. For $C$ irreducible algebraic we study the critical point correspondence and introduce the $\nu$- distance degree, generalizing the notion appearing in \cite{DHOST} for the Euclidean norm. Read More

We establish several mathematical and computational properties of the nuclear norm for higher-order tensors. We show that like tensor rank, tensor nuclear norm is dependent on the choice of base field --- the value of the nuclear norm of a real 3-tensor depends on whether we regard it as a real 3-tensor or a complex 3-tensor with real entries. We show that every tensor has a nuclear norm attaining decomposition and every symmetric tensor has a symmetric nuclear norm attaining decomposition. Read More

In many applications such as data compression, imaging or genomic data analysis, it is important to approximate a given tensor by a tensor that is sparsely representable. For matrices, i.e. Read More

Compressed sensing (CS) exploits the sparsity of a signal in order to integrate acquisition and compression. CS theory enables exact reconstruction of a sparse signal from relatively few linear measurements via a suitable nonlinear minimization process. Conventional CS theory relies on vectorial data representation, which results in good compression ratios at the expense of increased computational complexity. Read More

Let G be a finite subgroup of unitary matrices acting on the space of $N$-qubits. We associate with G a uniform quantum channel QU from the space on $N$-qubits to itself. We give a quantum algorithm to approximate this channel by considering a set of generators on G. Read More

Convex optimization problems arise naturally in quantum information theory, often in terms of minimizing a convex function over a convex subset of the space of hermitian matrices. In most cases, finding exact solutions to these problems is usually impossible. As inspired by earlier investigations into the relative entropy of entanglement [Phys. Read More

In the first part of this paper we study a best approximation of a vector in Euclidean space R^n with respect to a closed semi-algebraic set C and a given semi-algebraic norm. Assuming that the given norm and its dual norm are differentiable we show that a best approximation is unique outside a hypersurface. We then study the case where C is an irreducible variety and the approximation is with respect to the Euclidean norm. Read More

Let L(m,n) denote the convex set of completely positive trace preserving operators from C^{m x m} to C^{n x n}$, i.e quantum channels. We give a necessary condition for L in L(m,n) to be an extreme point. Read More

Compressive sensing (CS) has triggered enormous research activity since its first appearance. CS exploits the signal's sparsity or compressibility in a particular domain and integrates data compression and acquisition, thus allowing exact reconstruction through relatively few non-adaptive linear measurements. While conventional CS theory relies on data representation in the form of vectors, many data types in various applications such as color imaging, video sequences, and multi-sensor networks, are intrinsically represented by higher-order tensors. Read More

Uncertainty relations are a distinctive characteristic of quantum theory that impose intrinsic limitations on the precision with which physical properties can be simultaneously determined. The modern work on uncertainty relations employs \emph{entropic measures} to quantify the lack of knowledge associated with measuring non-commuting observables. However, there is no fundamental reason for using entropies as quantifiers; any functional relation that characterizes the uncertainty of the measurement outcomes defines an uncertainty relation. Read More

A nonzero nonnegative definite hermitian m by m matrix A has increasing principal minors if the value of each principle minor of A is not less than the value each of its subminors. For $m>1$ we show $A$ has increasing principal minors if and only if $A^{-1}$ exists and its diagonal entries are less or equal to 1. Read More

We give upper bounds on weighted perfect matchings in pfaffian graphs. These upper bounds are better than Bregman's upper bounds on the number of perfect matchings. We show that some of our upper bounds are sharp for 3 and 4-regular pfaffian graphs. Read More

This survey paper deals with upper and lower bounds on the number of $k$-matchings in regular graphs on $N$ vertices. For the upper bounds we recall the upper matching conjecture which is known to hold for perfect matchings. For the lower bounds we first survey the known results for bipartite graphs, and their continuous versions as the van der Waerden and Tverberg permanent conjectures and its variants. Read More

We show that a best rank one approximation to a real symmetric tensor, which in principle can be nonsymmetric, can be chosen symmetric. Furthermore, a symmetric best rank one approximation to a symmetric tensor is unique if the tensor does not lie on a certain real algebraic variety. Read More

In this paper we consider a linear homogeneous system of $m$ equations in $n$ unknowns with integer coefficients over the reals. Assume that the sum of the absolute values of the coefficients of each equation does not exceed $k+1$ for some positive integer $k$. We show that if the system has a nontrivial solution then there exists a nontrivial solution $\x=(x_1,. Read More

We show that the minimum von-Neumann entropy output of a quantum channel is locally additive. Hasting's counterexample for the additivity conjecture, makes this result quite surprising. In particular, it indicates that the non-additivity of the minimum entropy output is a global effect of quantum channels. Read More

We show that under a certain condition of local commutativity the minimum von-Neumann entropy output of a quantum channel is locally additive. We also show that local minima of the 2-norm entropy functions are closed under tensor products if one of the subspaces has dimension 2. Read More

We show that the irreducible variety of 4 x 4 x 4 complex valued tensors of border rank at most 4 is the zero set of polynomial equations of degree 5 (the Strassen commutative conditions), of degree 6 (the Landsberg-Manivel polynomials), and of degree 9 (the symmetrization conditions). Read More

We discuss here analogs of van der Waerden and Tverberg permanent conjectures for haffnians on the convex set of matrices whose extreme points are symmetric permutation matrices with zero diagonal. Read More

We show that the linear group of automorphism of Hermitian matrices which preserves the set of separable states is generated by \emph{natural} automorphisms: change of an orthonormal basis in each tensor factor, partial transpose in each tensor factor, and interchanging two tensor factors of the same dimension. We apply our results to preservers of the product numerical range. Read More

Let (lambda_d)(p) be the p monomer-dimer entropy on the d-dimensional integer lattice Z^d, where p in [0,1] is the dimer density. We give upper and lower bounds for (lambda_d)(p) in terms of expressions involving (lambda_(d-1))(q). The upper bound is based on a conjecture claiming that the p monomer-dimer entropy of an infinite subset of Z^d is bounded above by (lambda_d)(p). Read More

The relative entropy of entanglement is defined in terms of the relative entropy between an entangled state and its closest separable state (CSS). Given a multipartite-state on the boundary of the set of separable states, we find a closed formula for all the entangled state for which this state is a CSS. Quite amazing, our formula holds for multipartite states in all dimensions. Read More

In this paper we deal with two aspects of the minimum rank of a simple undirected graph $G$ on $n$ vertices over a finite field $\FF_q$ with $q$ elements, which is denoted by $\mr(\FF_q,G)$. In the first part of this paper we show that the average minimum rank of simple undirected labeled graphs on $n$ vertices over $\FF_2$ is $(1-\varepsilon_n)n$, were $\lim_{n\to\infty} \varepsilon_n=0$. In the second part of this paper we assume that $G$ contains a clique $K_k$ on $k$-vertices. Read More

We study tensors in $\C^{m\times n\times l}$ whose border rank is $l$. We characterize the tensors in $\C^{3\times 3\times 4}$ and in $\C^{4\times 4\times 4}$ of border rank 4 at most. Read More

We show that a nontrivial graph isomorphism problem of two undirected graphs, and more generally, the permutation similarity of two given $n\times n$ matrices, is equivalent to equalities of volumes of the induced three convex bounded polytopes intersected with a given sequence of balls, centered at the origin with radii $t_i\in (0,\sqrt{n-1})$, where $\{t_i\}$ is an increasing sequence converging to $\sqrt{n-1}$. These polytopes are characterized by $n^2$ inequalities in at most $n^2$ variables. The existence of fpras for computing volumes of convex bodies gives rise to a semi-frpas of order $O^*(n^{14})$ at most to find if given two undirected graphs are isomorphic. Read More

In this note we extend the necessary and sufficient conditions of Boyle-Handleman 1991 and Kim-Ormes-Roush 2000 for a nonzero eigenvalue multiset of primitive matrices over $\R_+$ and $\Z_+$, respectively, to irreducible matrices. Read More

In this paper we give necessary and sufficient conditions on a nonnegative tensor to be diagonally equivalent to a tensor with prescribed slice sums. These conditions are variations of Bapat-Raghavan and Franklin-Lorenz conditions. Read More

We study theoretical and computational properties of the pressure function for subshifts of finite type on the integer lattice $\Z^d$, multidimensional SOFT, which are called Potts models in mathematical physics. We show that the pressure is Lipschitz and convex. We use the properties of convex functions to show rigorously that the phase transition of the first order correspond exactly to the points where the pressure is not differentiable. Read More

Consider the polynomial $tr (A + tB)^m$ in $t$ for positive hermitian matrices $A$ and $B$ with $m \in \N$. The Bessis-Moussa-Villani conjecture (in the equivalent form of Lieb and Seiringer) states that this polynomial has nonnegative coefficients only. We prove that they are at least asymptotically positive, for the nontrivial case of $AB \neq 0$. Read More

In this paper we study the maximum value of the largest eigenvalue for simple bipartite graphs, where the number of edges is given and the number of vertices on each side of the bipartition is given. We state a conjectured solution, which is an analog of the Brualdi- Hoffman conjecture for general graphs, and prove the conjecture in some special cases. Read More

We introduce two additive invariants of output quantum channels. If the value of one these invariants is less than 1 then the logarithm of the inverse of its value is a positive lower bound for the regularized minimum entropy of an output quantum channel. We give a few examples in which one of these invariants is less than 1. Read More

We study the problem of maximizing sum rates in a Gaussian interference-limited channel that models multiuser communication in a CDMA wireless network or DSL cable binder. Using tools from nonnegative irreducible matrix theory, in particular the Perron-Frobenius Theorem and the Friedland-Karlin inequalities, we provide insights into the structural property of optimal power allocation strategies that maximize sum rates. Our approach is similar to the treatment of linear models in mathematical economies, where interference is viewed in the context of competition. Read More

We study the generic and typical ranks of 3-tensors of dimension l x m x n using results from matrices and algebraic geometry. We state a conjecture about the exact values of the generic rank of 3-tensors over the complex numbers, which is verified numerically for l,m,n not greater than 14. We also discuss the typical ranks over the real numbers, and give an example of an infinite family of 3-tensors of the form l=m, n=(m-1)^2+1, m=3,4,. Read More

We show that for fixed $A,B$, hermitian nonnegative definite matrices, and fixed $k$ the coefficients of the $t^k$ in the polynomial $\tr (A+tB)^m$ is positive if $\tr AB >0$ and $m>N(A,B,k)$. Read More

We show that the number of perfect matching in a simple graph $G$ with an even number of vertices and degree sequence $d_1,d_2, ... Read More

We give an upper bound on the number of perfect matchings in an undirected simple graph $G$ with an even number of vertices, in terms of the degrees of all the vertices in $G$. This bound is sharp if $G$ is a union of complete bipartite graphs. This bound is a generalization of the upper bound on the number of perfect matchings in bipartite graphs on $n+n$ vertices given by the Bregman-Minc inequality for the permanents of $(0,1)$ matrices. Read More

We relate the graph isomorphism problem to the solvability of certain systems of linear equations with nonnegative variables. This version replaces the two previous versions of this paper. Read More

We give a fully polynomial randomized approximation scheme to compute a lower bound for the matching polynomial of any weighted graph at a positive argument. For the matching polynomial of complete bipartite graphs with bounded weights these lower bounds are asymptotically optimal. Read More

We determine the extreme points and facets of the convex hull of all dual degree partitions of simple graphs on $n$ vertices. Read More

We show that the number of $k$-matching in a given undirected graph $G$ is equal to the number of perfect matching of the corresponding graph $G_k$ on an even number of vertices divided by a suitable factor. If $G$ is bipartite then one can construct a bipartite $G_k$. For bipartite graphs this result implies that the number of $k$-matching has a polynomial-time approximation algorithm. Read More