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

Inapproximability of Matrix $prightarrow q$ Norms

302   0   0.0 ( 0 )
 نشر من قبل Vijay Bhattiprolu
 تاريخ النشر 2018
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




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

We study the problem of computing the $prightarrow q$ norm of a matrix $A in R^{m times n}$, defined as [ |A|_{prightarrow q} ~:=~ max_{x ,in, R^n setminus {0}} frac{|Ax|_q}{|x|_p} ] This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=infty$, $q=1$), and has been widely studied in various regimes. When $p geq q$, the problem exhibits a dichotomy: constant factor approximation algorithms are known if $2 in [q,p]$, and the problem is hard to approximate within almost polynomial factors when $2 otin [q,p]$. The regime when $p < q$, known as emph{hypercontractive norms}, is particularly significant for various applications but much less well understood. The case with $p = 2$ and $q > 2$ was studied by [Barak et al, STOC12] who gave sub-exponential algorithms for a promise version of the problem (which captures small-set expansion) and also proved hardness of approximation results based on the Exponential Time Hypothesis. However, no NP-hardness of approximation is known for these problems for any $p < q$. We study the hardness of approximating matrix norms in both the above cases and prove the following results: - We show that for any $1< p < q < infty$ with $2 otin [p,q]$, $|A|_{prightarrow q}$ is hard to approximate within $2^{O(log^{1-epsilon}!n)}$ assuming $NP otsubseteq BPTIME(2^{log^{O(1)}!n})$. This suggests that, similar to the case of $p geq q$, the hypercontractive setting may be qualitatively different when $2$ does not lie between $p$ and $q$. - For all $p geq q$ with $2 in [q,p]$, we show $|A|_{prightarrow q}$ is hard to approximate within any factor than $1/(gamma_{p^*} cdot gamma_q)$, where for any $r$, $gamma_r$ denotes the $r^{th}$ norm of a gaussian, and $p^*$ is the dual norm of $p$.



قيم البحث

اقرأ أيضاً

A rainbow $q$-coloring of a $k$-uniform hypergraph is a $q$-coloring of the vertex set such that every hyperedge contains all $q$ colors. We prove that given a rainbow $(k - 2lfloor sqrt{k}rfloor)$-colorable $k$-uniform hypergraph, it is NP-hard to find a normal $2$-coloring. Previously, this was only known for rainbow $lfloor k/2 rfloor$-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow $(q, p)$-coloring, defined as a coloring using $q$ colors such that every hyperedge contains at least $p$ colors. We prove that given a rainbow $(k - lfloor sqrt{kc} rfloor, k- lfloor3sqrt{kc} rfloor)$-colorable $k$ uniform hypergraph, it is NP-hard to find a normal $c$-coloring for any $c = o(k)$. The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory. 1990) using topological methods and the other theorem we prove using a generalized Borsuk-Ulam theorem.
In this paper, we consider the Target Set Selection problem: given a graph and a threshold value $thr(v)$ for any vertex $v$ of the graph, find a minimum size vertex-subset to activate s.t. all the vertices of the graph are activated at the end of th e propagation process. A vertex $v$ is activated during the propagation process if at least $thr(v)$ of its neighbors are activated. This problem models several practical issues like faults in distributed networks or word-to-mouth recommendations in social networks. We show that for any functions $f$ and $rho$ this problem cannot be approximated within a factor of $rho(k)$ in $f(k) cdot n^{O(1)}$ time, unless FPT = W[P], even for restricted thresholds (namely constant and majority thresholds). We also study the cardinality constraint maximization and minimizati
We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable algorithms. The questions, which have been asked several times (e.g., [Marx08, FGMS12, DF13]), are whether there is a non-trivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting $text{OPT}$ be the optimum and $N$ be the size of the input, is there an algorithm that runs in $t(text{OPT})text{poly}(N)$ time and outputs a solution of size $f(text{OPT})$, for any functions $t$ and $f$ that are independent of $N$ (for Clique, we want $f(text{OPT})=omega(1)$)? In this paper, we show that both Clique and DomSet admit no non-trivial FPT-approximation algorithm, i.e., there is no $o(text{OPT})$-FPT-approximation algorithm for Clique and no $f(text{OPT})$-FPT-approximation algorithm for DomSet, for any function $f$ (e.g., this holds even if $f$ is the Ackermann function). In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis (Gap-ETH) [Dinur16, MR16], which states that no $2^{o(n)}$-time algorithm can distinguish between a satisfiable 3SAT formula and one which is not even $(1 - epsilon)$-satisfiable for some constant $epsilon > 0$. Besides Clique and DomSet, we also rule out non-trivial FPT-approximation for Maximum Balanced Biclique, Maximum Subgraphs with Hereditary Properties, and Maximum Induced Matching in bipartite graphs. Additionally, we rule out $k^{o(1)}$-FPT-approximation algorithm for Densest $k$-Subgraph although this ratio does not yet match the trivial $O(k)$-approximation algorithm.
A rigidity theory is developed for bar-joint frameworks in linear matrix spaces endowed with a unitarily invariant norm. Analogues of Maxwells counting criteria are obtained and minimally rigid matrix frameworks are shown to belong to the matroidal c lass of (k,l)-sparse graphs for suitable k and l. A characterisation of infinitesimal rigidity is obtained for product norms and it is shown that K_6 - e (respectively, K_7) is the smallest minimally rigid graph for the class of 2 x 2 symmetric (respectively, hermitian) matrices with the trace norm.
We propose COSMA: a parallel matrix-matrix multiplication algorithm that is near communication-optimal for all combinations of matrix dimensions, processor counts, and memory sizes. The key idea behind COSMA is to derive an optimal (up to a factor of 0.03% for 10MB of fast memory) sequential schedule and then parallelize it, preserving I/O optimality. To achieve this, we use the red-blue pebble game to precisely model MMM dependencies and derive a constructive and tight sequential and parallel I/O lower bound proofs. Compared to 2D or 3D algorithms, which fix processor decomposition upfront and then map it to the matrix dimensions, it reduces communication volume by up to $sqrt{3}$ times. COSMA outperforms the established ScaLAPACK, CARMA, and CTF algorithms in all scenarios up to 12.8x (2.2x on average), achieving up to 88% of Piz Daints peak performance. Our work does not require any hand tuning and is maintained as an open source implementation.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

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