ترغب بنشر مسار تعليمي؟ اضغط هنا

On the minimum trace norm of (0,1)-matrices

241   0   0.0 ( 0 )
 نشر من قبل Vladimir Nikiforov
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

The trace norm of a matrix is the sum of its singular values. This paper presents results on the minimum trace norm $psi_{n}left( mright) $ of $left( 0,1right) $-matrices of size $ntimes n$ with exactly $m$ ones. It is shown that: (1) if $ngeq2$ and $n<mleq2n,$ then $psi_{n}left( mright) leq sqrt{m+sqrt{2left( m-1right) }}$ , with equality if and only if $m$ is a prime; (2) if $ngeq4$ and $2n<mleq3n,$ then $psi_{n}left( mright) leq sqrt{m+2sqrt{2leftlfloor m/3rightrfloor }}$ , with equality if and only if $m$ is a prime or a double of a prime; (3) if $3n<mleq4n,$ then $psi_{n}left( mright) leqsqrt{m+2sqrt{m-2}}% $ , with equality if and only if there is an integer $kgeq1$ such that $m=12kpm2$ and $4kpm1,6kpm1,12kpm1$ are primes.



قيم البحث

اقرأ أيضاً

136 - A. A. Taranenko 2014
The permanent of a multidimensional matrix is the sum of products of entries over all diagonals. By Mincs conjecture, there exists a reachable upper bound on the permanent of 2-dimensional (0,1)-matrices. In this paper we obtain some generalizations of Mincs conjecture to the multidimensional case. For this purpose we prove and compare several bounds on the permanent of multidimensional (0,1)-matrices. Most estimates can be used for matrices with nonnegative bounded entries.
Using the $ell_1$-norm to regularize the estimation of the parameter vector of a linear model leads to an unstable estimator when covariates are highly correlated. In this paper, we introduce a new penalty function which takes into account the correl ation of the design matrix to stabilize the estimation. This norm, called the trace Lasso, uses the trace norm, which is a convex surrogate of the rank, of the selected covariates as the criterion of model complexity. We analyze the properties of our norm, describe an optimization algorithm based on reweighted least-squares, and illustrate the behavior of this norm on synthetic data, showing that it is more adapted to strong correlations than competing methods such as the elastic net.
The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i eq j$) is nonzero whenever ${i,j}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult par ameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7. This paper contains a list of minimum ranks for all graphs of order at most 7. We also present selected optimal matrices.
Evaluating adversarial robustness amounts to finding the minimum perturbation needed to have an input sample misclassified. The inherent complexity of the underlying optimization requires current gradient-based attacks to be carefully tuned, initiali zed, and possibly executed for many computationally-demanding iterations, even if specialized to a given perturbation model. In this work, we overcome these limitations by proposing a fast minimum-norm (FMN) attack that works with different $ell_p$-norm perturbation models ($p=0, 1, 2, infty$), is robust to hyperparameter choices, does not require adversarial starting points, and converges within few lightweight steps. It works by iteratively finding the sample misclassified with maximum confidence within an $ell_p$-norm constraint of size $epsilon$, while adapting $epsilon$ to minimize the distance of the current sample to the decision boundary. Extensive experiments show that FMN significantly outperforms existing attacks in terms of convergence speed and computation time, while reporting comparable or even smaller perturbation sizes.
72 - Andrew Schopieray 2020
We prove several results in the theory of fusion categories using the product (norm) and sum (trace) of Galois conjugates of formal codegrees. First, we prove that finitely-many fusion categories exist up to equivalence whose global dimension has a f ixed norm. Furthermore, with two exceptions, all formal codegrees of spherical fusion categories with square-free norm are rational integers. This implies, with three exceptions, that every spherical braided fusion category whose global dimension has prime norm is pointed. The reason exceptions occur is related to the classical Schur-Siegel-Smyth problem of describing totally positive algebraic integers of small absolute trace.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا