EE Student Information

The Department of Electrical Engineering supports Black Lives Matter. Read more.

• • • • 

 EE Student Information, Spring & Summer Quarters 19-20: FAQs and Updated EE Course List.

Updates will be posted on this page, as well as emailed to the EE student mail list.

Please see Stanford University Health Alerts for course and travel updates.

As always, use your best judgement and consider your own and others' well-being at all times.

IT-Forum

IT-Forum

Topic: 
Low-rank Estimation: Why Non-convex Gradient Descent Works
Abstract / Description: 

A large range of problems in statistics, machine learning and signal processing can be cast as fitting a structured low-rank matrix to noisy data. A popular approach to the resulting rank-constrained optimization problem is convex SDP relaxation, which runs in polynomial time in principle and enjoys desirable statistical guarantees. For large-scale problems, however, the (super-)quadratic time complexity of SDPs is often too high. An attractive alternative is to run projected gradient descent directly over the space of low-rank matrices. This approach is highly scalable, but its convergence and statistical accuracy were unclear due to non-convexity. Here we develop a unified framework characterizing the convergence of this non-convex method as well as the statistical properties of the resulting solutions. Our results provide insights into why we should expect non-convex methods to work in general, and yield global guarantees for a large number of concrete problems, including matrix completion with real and one-bit observations, matrix decomposition, robust and sparse PCA and graph clustering. Our framework is powerful enough to accommodate nonlinear measurements, matrices with arbitrary rank, and the noisy, constrained setting with additional structures in the noise and target matrices, and moreover does not require resampling.

Date and Time: 
Friday, April 1, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
When your big data seems too small: accurate inferences beyond the empirical distribution
Abstract / Description: 

We discuss two problems related to the general challenge of making accurate inferences about a complex distribution, in the regime in which the amount of data (i.e the sample size) is too small for the empirical distribution of the samples to be an accurate representation of the underlying distribution. The first problem is the task of accurately estimating the eigenvalues of the covariance matrix of a distribution--the "population spectrum". (These eigenvalues contain basic information about the distribution, including the presence/lack of low-dimensional structure in the distribution and the applicability of many higher-level machine learning and multivariate statistical tools.) As we show, even in the regime where the sample size is linear or sublinear in the dimensionality of the distribution, and hence the eigenvalues and eigenvectors of the empirical covariance matrix are misleading, accurate approximations to the true population spectrum are possible. In the second portion of the talk, we discuss the problem of recovering a low-rank approximation to a matrix of probabilities P, given access to an observed matrix of "counts" obtained via independent samples from the distribution defined by P. This problem can be viewed as a generalization of "community detection", and is relevant to several recent machine learning efforts, including the work on constructing "word embeddings".

Date and Time: 
Friday, February 12, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Asymptotically tight bounds on the depth of estimated context trees
Abstract / Description: 

We study the maximum depth of context tree estimates, i.e., the maximum Markov order attainable by an estimated tree model given an input sequence of length n. We consider two classes of estimators:

1) Penalized maximum likelihood (PML) estimators where a context tree T is obtained by minimizing a cost of the form -log P_T(x^n) + f(n)|S_T|, where P_T(x^n) is the ML probability of the input sequence x^n under a tree model T, S_T is the set of states defined by T, and f(n) is an increasing (penalization) function of n (the popular BIC estimator corresponds to f(n)= (A-1)/2 log n, where A is the size of the input alphabet).

2) MDL estimators based on the KT probability assignment. In each case we derive an asymptotic upper bound, n^{1/2 + o(1)}, and we exhibit explicit input sequences that show that this bound is asymptotically tight up to the term o(1) in the exponent.

It is based on joint work with Gadiel Seroussi.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Kartik Venkat. To suggest speakers, please contact any of the students.

Date and Time: 
Friday, February 5, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Computational Limits in Statistical Inference: Hidden Cliques and Sum of Squares
Abstract / Description: 

Characterizing the computational complexity of statistical inference problems is an outstanding open problem. This is gaining increasing importance given the ubiquity of large scale data analysis and algorithms in application domains as diverse as genomics, healthcare, finance and social sciences. The hidden clique problem is a prototypical example of an inference problem wherein computational constraints dramatically alter the inference ability. The hidden clique problem posits to find a "hidden" or "planted" clique (a densely connected set of vertices) within an otherwise random Erdos-Renyi graph. Unfortunately, standard reduction tools from theoretical computer science to demonstrate hardness fail to capture statistical nature of the hidden clique problem. I will describe a framework based on the powerful Sum-of-Squares (SOS) technique for characterizing computational difficulty in the hidden clique and other related problems. The analysis of the SOS algorithms requires controlling the spectra of random matrices of a non-standard type. I will describe a set of results that represent the state-of-the-art in proving lower bounds for the hidden clique and related problems.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Kartik Venkat. To suggest speakers, please contact any of the students.

Date and Time: 
Friday, January 22, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Multiple Testing and Adaptive Estimation via the Sorted L-One Norm
Abstract / Description: 

In many real-world statistical problems, we observe a large number of potentially explanatory variables of which a majority may be irrelevant. For this type of problem, controlling the false discovery rate (FDR) guarantees that most of the discoveries are truly explanatory and thus replicable. In this talk, we propose a new method named SLOPE to control the FDR in sparse high-dimensional linear regression. This computationally efficient procedure works by regularizing the fitted coefficients according to their ranks: the higher the rank, the larger the penalty. This is analogous to the Benjamini-Hochberg procedure, which compares more significant p-values with more stringent thresholds. Whenever the columns of the design matrix are not strongly correlated, we show empirically that SLOPE obtains FDR control at a reasonable level while offering substantial power.

Although SLOPE is developed from a multiple testing viewpoint, we show the surprising result that it achieves optimal squared errors under Gaussian random designs over a wide range of sparsity classes. An appealing feature is that SLOPE does not require any knowledge of the degree of sparsity. This adaptivity to unknown sparsity has to do with the FDR control, which strikes the right balance between bias and variance. The proof of this result presents several elements not found in the high-dimensional statistics literature.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

The Information Theory Forum is organized by graduate students Jiantao Jiao and Kartik Venkat. To suggest speakers, please contact any of the students.

Date and Time: 
Friday, January 15, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Improving on the Cut-Set Bound via Geometric Analysis of Typical Sets
Abstract / Description: 

The cut-set bound developed by (Cover and El Gamal, 1979) has since remained the best known upper bound on the capacity of the Gaussian relay channel. We develop a new upper bound on the capacity of the Gaussian primitive relay channel which is tighter than the cut-set bound. Combined with a simple tensorization argument proposed by (Courtade and Ozgur, 2015), our result also implies that the current capacity approximations for Gaussian relay networks, which have linear gap to the cut-set bound in the number of nodes, are order-optimal and leads to a lower bound on the pre-constant.

Our approach for developing the new bound significantly deviates from the standard information-theoretic approach for proving upper bounds on the capacity of multi-user channels. We build on measure concentration to analyze the geometric probabilistic relations between the typical sets of the n-letter random variables associated with a reliable code for communicating over the channel. These relations translate to new entropy inequalities between the n-letter random variables involved. Our approach can be extended to the discrete memoryless relay channel, and in particular, can be used to obtain surprising insights on a long-standing open problem posed by (Cover, 1987), namely, what is the minimum required relay-to-destination communication rate in order for the capacity of the relay channel to be equal to that of the broadcast cut.

Date and Time: 
Friday, January 8, 2016 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Capacity bounds for diamond networks with an orthogonal broadcast channel
Abstract / Description: 

A class of diamond networks is studied where the broadcast component is orthogonal and modeled by two independent bit-pipes. New upper and lower bounds on the capacity are derived. The proof technique for the upper bound generalizes bounding techniques of Ozarow for the Gaussian multiple description problem (1981) and Kang and Liu for the Gaussian diamond network (2011). The lower bound is based on Marton's coding technique and superposition coding. The bounds are evaluated for Gaussian and binary adder multiple access channels (MACs). For Gaussian MACs, both the lower and upper bounds strengthen the Kang-Liu bounds and establish capacity for interesting ranges of bit-pipe capacities. For binary adder MACs, the capacity is established for all ranges of bit-pipe capacities.


The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

 

 

Date and Time: 
Friday, December 4, 2015 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Super-Resolution of Positive Sources
Abstract / Description: 

The resolution of all microscopes is limited by diffraction. The observed signal is a convolution of the emitted signal with a low-pass kernel, the point-spread function (PSF) of the microscope. The frequency cut-off of the PSF is inversely proportional to the wavelength of light. Hence, the features of the object that are smaller than the wavelength of light are difficult to observe. In single-molecule microscopy the emitted signal is a collection of point sources, produced by blinking molecules. The goal is to recover the location of these sources with precision that is much higher than the wavelength of light. This leads to the problem of super-resolution of positive sources in the presence of noise. We show that the problem can be solved using convex optimization in a stable fashion. The stability of reconstruction depends on Rayleigh-regularity of the support of the signal, i.e., on how many point sources can occur within an interval of one wavelength. The stability estimate is complemented by a converse result: the performance of the convex algorithm is nearly optimal. I will also give a brief summary on the ongoing project, developed in collaboration with the group of Prof. W.E. Moerner, where we use the theoretical ideas to improve microscopes.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

Date and Time: 
Friday, November 20, 2015 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
Understanding synergistic interactions and complex information sharing
Abstract / Description: 

The interactions between three or more variables are frequently nontrivial, poorly understood, and yet, are paramount for future advances in fields such as multiuser information theory, neuroscience and complexity science. In this talk, we will study the interactions that can exist between a group of random variables by introducing a axiomatic framework that characterizes the ways in which information can be shared. The framework is based on the novel notion of information synergy, which measures statistical structures that are present in the whole set of variables but not in the any of them individually. Finally, the framework will be applied to several communication scenarios, providing a more intuitive understanding of their fundamental limits.


 

The Information Theory Forum (IT-Forum) at Stanford ISL is an interdisciplinary academic forum which focuses on mathematical aspects of information processing. With a primary emphasis on information theory, we also welcome researchers from signal processing, learning and statistical inference, control and optimization to deliver talks at our forum. We also warmly welcome industrial affiliates in the above fields. The forum is typically held in Packard 202 every Friday at 1:00 pm during the academic year.

Date and Time: 
Friday, November 13, 2015 - 1:00pm to 2:00pm
Venue: 
Packard 202

IT-Forum

Topic: 
A Stronger Soft-Covering Lemma that assures Semantic Security in Wiretap Channels
Abstract / Description: 

In 1975, Wyner published two very different papers that are unexpectedly connected. One introduced the wiretap channel, showing that information-theoretic secrecy is possible without a secret key by taking advantage of channel noise. This is the foundation for much of physical-layer security. The other paper introduced a notion of common information relevant to generating random variables at different terminals. In that work he introduced a soft-covering tool for proving achievability. Coincidently, soft covering has now become the tool of choice for proving strong secrecy in wiretap channels, although Wyner didn't appear to make any connection between the two results.

We present a sharpening of the soft-covering tool by showing that the soft-covering phenomenon happens with doubly-exponential certainty with respect to a randomly generated codebook. Through the union bound, this enables security proofs in settings where many security constraints must be satisfied simultaneously. The "type II" wiretap channel is a great example of this, where the eavesdropper can actively influence his observations but security must hold in all cases. We demonstrate the effectiveness of this tool by deriving the secrecy capacity of wiretap channels of type II with a noisy main channel---previously an open problem. Additionally, this stronger soft covering allows information-theoretic security proofs to be easily upgraded to semantic security, which is the gold standard in cryptography.

Date and Time: 
Friday, November 6, 2015 - 1:00pm to 2:00pm
Venue: 
Packard 202

Pages

Subscribe to RSS - IT-Forum