TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-q tensor A ∈ R ∏q i=1 ni , output a rank-k tensor B for which ‖A − B‖F ≤ (1 + ) OPT, where OPT = infrank-k A′ ‖A − A‖F . Despite much success on obtaining relative error low rank approximations for matrices, no such results were known for tensors. One structural issue is that there may be no rank-k tensor Ak achieving the above infinum. Another, computational issue, is that an efficient relative error low rank approximation algorithm for tensors would allow one to compute the rank of a tensor, which is NP-hard. We bypass these two issues via (1) bicriteria and (2) parameterized complexity solutions: 1. We give an algorithm which outputs a rank k′ = O((k/ )q−1) tensor B for which ‖A − B‖F ≤ (1+ ) OPT in nnz(A)+n ·poly(k/ ) time in the real RAM model, whenever either Ak exists or OPT > 0. Here nnz(A) denotes the number of non-zero entries in A. If both Ak does not exist and OPT = 0, then B instead satisfies ‖A − B‖F < γ, where γ is any positive, arbitrarily small function of n. 2. We give an algorithm for any δ > 0 which outputs a rank k tensor B for which ‖A−B‖F ≤ (1+ ) OPT and runs in (nnz(A)+n poly(k/ )+exp(k/ )) ·nδ time in the unit cost RAM model, whenever OPT > 2−O(n ) and there is a rank-k tensor B = ∑k i=1 ui ⊗ vi ⊗ wi for which ‖A − B‖F ≤ (1 + /2) OPT and ‖ui‖2, ‖vi‖2, ‖wi‖2 ≤ 2 δ). If OPT ≤ 2−Ω(nδ), then B instead satisfies ‖A−B‖F ≤ 2−Ω(n δ). Our first result is polynomial time, and in fact input sparsity time, in n, k, and 1/ , for any k ≥ 1 and any 0 < < 1, while our second result is fixed parameter tractable in k and 1/ . For outputting a rank-k tensor, or even a bicriteria solution with rank-Ck for a certain constant C > 1, we show a 2 1−o(1)) time lower bound under the Exponential Time Hypothesis. Our results are based on an “iterative existential argument”, and give the first relative error low rank approximations for tensors for a large number of error measures for which nothing was known. In particular, we give the first relative error approximation algorithms on tensors for: column row and tube subset selection, entrywise `p-low rank approximation for 1 ≤ p < 2, low rank approximation with respect to sum of Euclidean norms of faces or tubes, weighted low rank approximation, and low rank approximation in distributed and streaming models. We also obtain several new results for matrices, such as nnz(A)-time CUR decompositions, improving the previous nnz(A) log n-time CUR decompositions, which may be of independent interest. ∗Work done while visiting IBM Almaden, and supported in part by UTCS TAship (CS361 Spring 17 Introduction to Computer Security). †Supported in part by Simons Foundation, and NSF CCF-1617955. ar X iv :1 70 4. 08 24 6v 1 [ cs .D S] 2 6 A pr 2 01 7

SOLUTION: Relative Error Tensor Low Rank Approximation

PROBLEM: The field of speech recognition is in the midst of a paradigm shift: end-to-end neural networks are challenging the dominance of hidden Markov models as a core technology. Using an attention mechanism in a recurrent encoder-decoder architecture solves the dynamic time alignment problem, allowing joint end-to-end training of the acoustic and language modeling components. In this paper we extend the end-to-end framework to encompass microphone array signal processing for noise suppression and speech enhancement within the acoustic encoding network. This allows the beamforming components to be optimized jointly within the recognition architecture to improve the end-to-end speech recognition objective. Experiments on the noisy speech benchmarks (CHiME-4 and AMI) show that our multichannel end-to-end system outperformed the attention-based baseline with input from a conventional adaptive beamformer.

SOLUTION: Multichannel End-to-end Speech Recognition 

PROBLEM: We consider the problem of learning a causal graph over a set of variables with interventions. We study the cost-optimal causal graph learning problem: For a given skeleton (undirected version of the causal graph), design the set of interventions with minimum total cost, that can uniquely identify any causal graph with the given skeleton. We show that this problem is solvable in polynomial time. Later, we consider the case when the number of interventions is limited. For this case, we provide polynomial time algorithms when the skeleton is a tree or a clique tree. For a general chordal skeleton, we develop an efficient greedy algorithm, which can be improved when the causal graph skeleton is an interval graph.

SOLUTION:
Cost-Optimal Learning of Causal Graphs