Title: SNIPE for memory-limited PCA with incomplete data: From failure to success
Abstract: Consider the problem of identifying an unknown subspace S from data with erasures and with limited memory available. Suppose we form the measurements into blocks and iteratively update our estimate of S with each new block. In the first part of this talk, we will discuss why estimating S by computing the “running average” of span of these blocks fails in general. Based on the lessons learned, we then propose SNIPE for memory-limited PCA with incomplete data, useful also for streaming data applications. SNIPE provably converges (linearly) to the true subspace, in the absence of noise and with sufficient measurements. This is joint work with Laura Balzano and Mike Wakin.
Biography: Armin Eftekhari received his PhD in 2015 at Colorado School of Mines, under the supervision of Mike Wakin (EE). After that, he worked with Rachel Ward (Math, UT Austin) as an ICES postdoc fellow. This summer, he is a postdoc with Ping Li (CS & Stats, Rutgers). He is joining the Alan Turing Institute as a postdoc next month to work with Jared Tanner (Math, Oxford).
Title: Minimax Lower Bounds on Dictionary Learning for Tensor Data
Abstract: This talk provides fundamental limits on the sample complexity of estimating dictionaries for tensor data. The specific focus of this work is on K-dimensional tensor data, in which case the underlying dictionary can be expressed in terms of K smaller dictionaries. The data are generated by linear combinations of these structured dictionary atoms and observed through white Gaussian noise. This work first provides a general lower bound on the minimax risk of dictionary learning for tensor data and then adapts the proof techniques for equivalent results in the case of sparse and sparse-Gaussian linear combinations. The results suggest the sample complexity of dictionary learning for tensor data can be significantly lower than that for unstructured data: for unstructured data it scales linearly with the product of the dictionary dimensions, whereas it need only scale linearly with the sum of the product of the dimensions of the (smaller) component dictionaries for tensor data. A partial converse is provided for the case of 2-dimensional tensor data. This involves developing an algorithm for learning of highly structured dictionaries from noisy tensor data and showing that it achieves one of the derived minimax lower bounds derived. Finally, numerical experiments highlight the advantages associated with explicitly accounting for tensor data structure during dictionary learning.
Biography: Zahra Shakeri is a senior ECE PhD student working under the supervision of Prof. Waheed Bajwa at Rutgers University. She received her BS at Sharif University of Technology in 2013 and her MS at Rutgers University in 2016. Her research interests include statistical signal processing and machine learning.
Title: Network Equivalence for Arbitrarily Varying and Compound Channels
Abstract: We address the problem of finding the capacity of noisy networks with either independent point-to-point compound channels (CC) or arbitrarily varying channels (AVC). These channels model the presence of a Byzantine adversary which controls a subset of links or nodes in the network. We derive equivalence results showing that these point-to-point channels with state can be replaced by noiseless bit-pipes without changing the network capacity region. Exact equivalence results are found for the CC model, and for some instances of the AVC, including all nonsymmetrizable AVCs. These results show that a feedback path between the output and input of a CC can increase the equivalent capacity, and that if common randomness can be established between the terminals of an AVC (either by feedback, a forward path, or via a third-party node), then again the equivalent capacity can increase. We also analyze an example involving an AVC for which no fixed-capacity bit-pipe is equivalent. Finally, as a generalization we consider a joint CC-AVC model, where the adversary chooses k channels with a CC-type state and controls the state sequences for each of these channels in an AVC-type fashion. If the network is fully connected we provide a simple expression for the capacity region of the noisy network. We also provide a necessary and sufficient condition for full connectivity, making use of a new condition for an AVC termed overwritability.
Biography: Dr. Joerg Kliewer received the Dipl.-Ing. (MSEE) degree in Electrical Engineering from the Hamburg University of Technology, Hamburg, Germany, in 1993 and the Dr.-Ing. degree (Ph.D.) in Electrical Engineering from the University of Kiel, Kiel, Germany, in 1999, respectively. From 1993 to 1998 he was a Research Assistant at the University of Kiel, Germany, and from 1999 to 2004, he was a Senior Researcher and Lecturer with the same institution. In 2004, he visited the University of Southampton, Southampton, U.K., for one year, and from 2005 until 2007, he was with the University of Notre Dame, Notre Dame, IN, as a Visiting Assistant Professor. From August 2007 until December 2013 he was with New Mexico State University, Las Cruces, NM, as an as an Assistant and most recently as an Associate Professor. In January 2014 he joined the New Jersey Institute of Technology, Newark, NJ, as an Associate Professor. His research interests span coding and information theory, graphical models, and statistical algorithms, which includes application to networked communication and security, data storage, and biology. Dr. Kliewer was the recipient of a Leverhulme Trust Award and a German Research Foundation Fellowship Award in 2003 and 2004, respectively. He was Associate Editor of the IEEE Transactions on Communications from 2008-2014 and now serves as an area editor for the same journal since 2015. He is also member of the editorial board of the IEEE Information Theory Society Newsletter since 2010 and serves as chair of the outreach committee for the same society since 2012.
Title: MSICA: ICA Based Transformation For Multi-Scale Decomposition With Application in Denoising
Abstract: A new method for muti-scale decomposition–called MSICA–is proposed to translate an original signal into multiple statistically independent scales. We prove that extracting the independent components of the even and odd samples of a signal results in the decomposition of the same into approximation and detail. We also show that the whitening procedure in Independent Component Analysis (ICA) is equivalent to a filter bank structure. Moreover, we examine the performance of MSICA in signal denoising and exploit the statistical independency of the approximation and detail to propose a novel signal-denoising strategy for multi-channel transmissions. Simulation results verify that MSICA can improve reliability in noisy channels in the case of multi-channel transmissions.
Biography: Abolfazl Hajisami is a student in Electrical and Computer Engineering (ECE) department at Rutgers University, NJ, where he is pursuing a PhD under the guidance of Dr. D. Pompili at the Cyber-Physical Systems Laboratory (CPS-Lab). He received his MSc and BSc Degrees from Sharif University of Technology and from Shahid Beheshti University (Tehran, Iran), respectively. In his MSc thesis, he worked on the application of blind source separation to image watermarking. Currently, he is working on elastic resource provisioning and allocation in Cloud Radio Access Networks.
Title: Locality in Coding Theory and the Gilbert-Varshamov Bound
Abstract: One of the main open problems in Coding Theory is to characterize the tradeoff between the rate and the minimum distance of a binary code. The best known tradeoff is the Gilbert-Varshamov bound. Another central question in Coding Theory is to analyze special properties that such codes with good rate-distance tradeoff may have. One property that has found many applications in theory as well as in practice is the property of locality in a code. In this talk we will survey classical aspects of Coding Theory, with a focus on the importance of locality in Error Correcting Codes. We will provide the motivations for locality, the standard concepts of “local codes,” and describe our main result, which is the first (randomized) construction of a family of local codes with rate-distance tradeoffs approaching the Gilbert-Varshamov bound. (Joint work with Sivakanth Gopi, Swastik Kopparty, Noga Ron-Zewi and Shubhangi Saraf.)
Biography: Rafael Oliveira is a fifth-year Ph.D. student in the Department of Computer Science at Princeton University, where he works with Prof. Dvir. He is broadly interested in the interplay between Mathematics and Computer Science. In particular, he is interested in the interplay between Algebra, Analysis, Combinatorics, Number Theory and Complexity Theory.