BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Parikshit Shah

Parikshit Shah appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCInformation Theorymath.ITMachine LearningSystems and ControlComputer Science and Game TheoryData Structures and Algorithmsmath.STMethodologyStatistics Theory

Catalog footprint

What is connected

12works
10topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

12 published item(s)

preprint2022arXiv

Robust and fair work allocation

In today's digital world, interaction with online platforms is ubiquitous, and thus content moderation is important for protecting users from content that do not comply with pre-established community guidelines. Having a robust content moderation system throughout every stage of planning is particularly important. We study the short-term planning problem of allocating human content reviewers to different harmful content categories. We use tools from fair division and study the application of competitive equilibrium and leximin allocation rules. Furthermore, we incorporate, to the traditional Fisher market setup, novel aspects that are of practical importance. The first aspect is the forecasted workload of different content categories. We show how a formulation that is inspired by the celebrated Eisenberg-Gale program allows us to find an allocation that not only satisfies the forecasted workload, but also fairly allocates the remaining reviewing hours among all content categories. The resulting allocation is also robust as the additional allocation provides a guardrail in cases where the actual workload deviates from the predicted workload. The second practical consideration is time dependent allocation that is motivated by the fact that partners need scheduling guidance for the reviewers across days to achieve efficiency. To address the time component, we introduce new extensions of the various fair allocation approaches for the single-time period setting, and we show that many properties extend in essence, albeit with some modifications. Related to the time component, we additionally investigate how to satisfy markets' desire for smooth allocation (e.g., partners for content reviewers prefer an allocation that does not vary much from time to time, to minimize staffing switch). We demonstrate the performance of our proposed approaches through real-world data obtained from Meta.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

False Discovery and Its Control in Low Rank Estimation

Models specified by low-rank matrices are ubiquitous in contemporary applications. In many of these problem domains, the row/column space structure of a low-rank matrix carries information about some underlying phenomenon, and it is of interest in inferential settings to evaluate the extent to which the row/column spaces of an estimated low-rank matrix signify discoveries about the phenomenon. However, in contrast to variable selection, we lack a formal framework to assess true/false discoveries in low-rank estimation; in particular, the key source of difficulty is that the standard notion of a discovery is a discrete one that is ill-suited to the smooth structure underlying low-rank matrices. We address this challenge via a geometric reformulation of the concept of a discovery, which then enables a natural definition in the low-rank case. We describe and analyze a generalization of the Stability Selection method of Meinshausen and Bühlmann to control for false discoveries in low-rank estimation, and we demonstrate its utility compared to previous approaches via numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Forward - Backward Greedy Algorithms for Atomic Norm Regularization

In many signal processing applications, the aim is to reconstruct a signal that has a simple representation with respect to a certain basis or frame. Fundamental elements of the basis known as "atoms" allow us to define "atomic norms" that can be used to formulate convex regularizations for the reconstruction problem. Efficient algorithms are available to solve these formulations in certain special cases, but an approach that works well for general atomic norms, both in terms of speed and reconstruction accuracy, remains to be found. This paper describes an optimization algorithm called CoGEnT that produces solutions with succinct atomic representations for reconstruction problems, generally formulated with atomic-norm constraints. CoGEnT combines a greedy selection scheme based on the conditional gradient approach with a backward (or "truncation") step that exploits the quadratic nature of the objective to reduce the basis size. We establish convergence properties and validate the algorithm via extensive numerical experiments on a suite of signal processing applications. Our algorithm and analysis also allow for inexact forward steps and for occasional enhancements of the current representation to be performed. CoGEnT can outperform the basic conditional gradient method, and indeed many methods that are tailored to specific applications, when the enhancement and truncation steps are defined appropriately. We also introduce several novel applications that are enabled by the atomic-norm framework, including tensor completion, moment problems in signal processing, and graph deconvolution.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice

Tensors play a central role in many modern machine learning and signal processing applications. In such applications, the target tensor is usually of low rank, i.e., can be expressed as a sum of a small number of rank one tensors. This motivates us to consider the problem of low rank tensor recovery from a class of linear measurements called separable measurements. As specific examples, we focus on two distinct types of separable measurement mechanisms (a) Random projections, where each measurement corresponds to an inner product of the tensor with a suitable random tensor, and (b) the completion problem where measurements constitute revelation of a random set of entries. We present a computationally efficient algorithm, with rigorous and order-optimal sample complexity results (upto logarithmic factors) for tensor recovery. Our method is based on reduction to matrix completion sub-problems and adaptation of Leurgans' method for tensor decomposition. We extend the methodology and sample complexity results to higher order tensors, and experimentally validate our theoretical results.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Relative Entropy Relaxations for Signomial Optimization

Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are non-convex optimization problems in general, and families of NP-hard problems can be reduced to SPs. In this paper we describe a hierarchy of convex relaxations to obtain successively tighter lower bounds of the optimal value of SPs. This sequence of lower bounds is computed by solving increasingly larger-sized relative entropy optimization problems, which are convex programs specified in terms of linear and relative entropy functions. Our approach relies crucially on the observation that the relative entropy function -- by virtue of its joint convexity with respect to both arguments -- provides a convex parametrization of certain sets of globally nonnegative signomials with efficiently computable nonnegativity certificates via the arithmetic-geometric-mean inequality. By appealing to representation theorems from real algebraic geometry, we show that our sequences of lower bounds converge to the global optima for broad classes of SPs. Finally, we also demonstrate the effectiveness of our methods via numerical experiments.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Compressed Sensing off the Grid

We consider the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0,1]. We propose an atomic norm minimization approach to exactly recover the unobserved samples. We reformulate this atomic norm minimization as an exact semidefinite program. Even with this continuous dictionary, we show that most sampling sets of size O(s log s log n) are sufficient to guarantee the exact frequency estimation with high probability, provided the frequencies are well separated. Numerical experiments are performed to illustrate the effectiveness of the proposed method.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Conic Geometric Programming

We introduce and study conic geometric programs (CGPs), which are convex optimization problems that unify geometric programs (GPs) and conic optimization problems such as semidefinite programs (SDPs). A CGP consists of a linear objective function that is to be minimized subject to affine constraints, convex conic constraints, and upper bound constraints on sums of exponential and affine functions. The conic constraints are the central feature of conic programs such as SDPs, while upper bounds on combined exponential/affine functions are generalizations of the types of constraints found in GPs. The dual of a CGP involves the maximization of the negative relative entropy between two nonnegative vectors jointly, subject to affine and conic constraints on the two vectors. Although CGPs contain GPs and SDPs as special instances, computing global optima of CGPs is not much harder than solving GPs and SDPs. More broadly, the CGP framework facilitates a range of new applications that fall outside the scope of SDPs and GPs. Specifically, we demonstrate the utility of CGPs in providing solutions to problems such as permanent maximization, hitting-time estimation in dynamical systems, the computation of the capacity of channels transmitting quantum information, and robust optimization formulations of GPs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Sketching Sparse Matrices

This paper considers the problem of recovering an unknown sparse p\times p matrix X from an m\times m matrix Y=AXB^T, where A and B are known m \times p matrices with m << p. The main result shows that there exist constructions of the "sketching" matrices A and B so that even if X has O(p) non-zeros, it can be recovered exactly and efficiently using a convex program as long as these non-zeros are not concentrated in any single row/column of X. Furthermore, it suffices for the size of Y (the sketch dimension) to scale as m = O(\sqrt{# nonzeros in X} \times log p). The results also show that the recovery is robust and stable in the sense that if X is equal to a sparse matrix plus a perturbation, then the convex program we propose produces an approximation with accuracy proportional to the size of the perturbation. Unlike traditional results on sparse recovery, where the sensing matrix produces independent measurements, our sensing operator is highly constrained (it assumes a tensor product structure). Therefore, proving recovery guarantees require non-standard techniques. Indeed our approach relies on a novel result concerning tensor products of bipartite graphs, which may be of independent interest. This problem is motivated by the following application, among others. Consider a p\times n data matrix D, consisting of n observations of p variables. Assume that the correlation matrix X:=DD^{T} is (approximately) sparse in the sense that each of the p variables is significantly correlated with only a few others. Our results show that these significant correlations can be detected even if we have access to only a sketch of the data S=AD with A \in R^{m\times p}.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Linear System Identification via Atomic Norm Regularization

This paper proposes a new algorithm for linear system identification from noisy measurements. The proposed algorithm balances a data fidelity term with a norm induced by the set of single pole filters. We pose a convex optimization problem that approximately solves the atomic norm minimization problem and identifies the unknown system from noisy linear measurements. This problem can be solved efficiently with standard, freely available software. We provide rigorous statistical guarantees that explicitly bound the estimation error (in the H_2-norm) in terms of the stability radius, the Hankel singular values of the true system and the number of measurements. These results in turn yield complexity bounds and asymptotic consistency. We provide numerical experiments demonstrating the efficacy of our method for estimating linear systems from a variety of linear measurements.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

An Optimal Controller Architecture for Poset-Causal Systems

We propose a novel and natural architecture for decentralized control that is applicable whenever the underlying system has the structure of a partially ordered set (poset). This controller architecture is based on the concept of Moebius inversion for posets, and enjoys simple and appealing separation properties, since the closed-loop dynamics can be analyzed in terms of decoupled subsystems. The controller structure provides rich and interesting connections between concepts from order theory such as Moebius inversion and control-theoretic concepts such as state prediction, correction, and separability. In addition, using our earlier results on H_2-optimal decentralized control for arbitrary posets, we prove that the H_2-optimal controller in fact possesses the proposed structure, thereby establishing the optimality of the new controller architecture.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Group Symmetry and Covariance Regularization

Statistical models that possess symmetry arise in diverse settings such as random fields associated to geophysical phenomena, exchangeable processes in Bayesian statistics, and cyclostationary processes in engineering. We formalize the notion of a symmetric model via group invariance. We propose projection onto a group fixed point subspace as a fundamental way of regularizing covariance matrices in the high-dimensional regime. In terms of parameters associated to the group we derive precise rates of convergence of the regularized covariance matrix and demonstrate that significant statistical gains may be expected in terms of the sample complexity. We further explore the consequences of symmetry on related model-selection problems such as the learning of sparse covariance and inverse covariance matrices. We also verify our results with simulations.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

H_2-Optimal Decentralized Control over Posets: A State-Space Solution for State-Feedback

We develop a complete state-space solution to H_2-optimal decentralized control of poset-causal systems with state-feedback. Our solution is based on the exploitation of a key separability property of the problem, that enables an efficient computation of the optimal controller by solving a small number of uncoupled standard Riccati equations. Our approach gives important insight into the structure of optimal controllers, such as controller degree bounds that depend on the structure of the poset. A novel element in our state-space characterization of the controller is a remarkable pair of transfer functions, that belong to the incidence algebra of the poset, are inverses of each other, and are intimately related to prediction of the state along the different paths on the poset. The results are illustrated by a numerical example.

0 citations0 reviewsNo code linkedOpen access