Linear function

In mathematics, the term linear function refers to two distinct but related notions:

In calculus and related areas, a linear function is a function whose graph is a straight line, that is, a polynomial function of degree zero or one. For distinguishing such a linear function from the other concept, the term affine function is often used.
In linear algebra, mathematical analysis, and functional analysis, a linear function is a linear map.

As a polynomial function Linear function (calculus) In calculus, analytic geometry and related areas, a linear function is a polynomial of degree one or less, including the zero polynomial (the latter not being considered to have degree zero). When the function is of only one variable, it is of the form :f(x)=ax+b, where ''a'' and ''b'' are constants, often real numbers. The graph of such a function of one variable is a nonvertical line. ''a'' is frequently referred to as the slope

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (21)

Related publications

Related people

Related units

Related concepts (32)

Related concepts

Related courses (74)

Related courses

Related lectures (152)

Related lectures

Function (mathematics)

In mathematics, a function from a set X to a set Y assigns to each element of X exactly one element of Y. The set X is called the dom

Field (mathematics)

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined and behave as the corresponding operations on rational and real numbers do. A field is thus

Linear algebra

Linear algebra is the branch of mathematics concerning linear equations such as: :a_1x_1+\cdots +a_nx_n=b, linear maps such as: :(x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,

Submodular Stochastic Probing on Matroids

Marek Adamczyk, Justin Dean Ward

In a stochastic probing problem we are given a universe E, and a probability that each element e in E is active. We determine if an element is active by probing it, and whenever a probed element is active, we must permanently include it in our solution. Moreover, throughout the process we need to obey inner constraints on the set of elements taken into the solution, and outer constraints on the set of all probed elements. All previous algorithmic results in this framework have considered only the problem of maximizing a linear function of the active elements. Here, we consider submodular objectives. We provide new, constant-factor approximations for maximizing a monotone submodular function subject to multiple matroid constraints on both the elements that may be taken and the elements that may be probed. We also obtain an improved approximation for linear objective functions, and show how our approach may be generalized to handle k-matchoid constraints.

INFORMS2016

The Sketching Complexity of Graph and Hypergraph Counting

John Michael Goddard Kallaugher, Mikhail Kapralov

Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been studied extensively in the literature, but many natural settings are still not well understood. In this paper we revisit the subgraph (and hypergraph) counting problem in the sketching model, where the algorithm's state as it processes a stream of updates to the graph is a linear function of the stream. This model has recently received a lot of attention in the literature, and has become a standard model for solving dynamic graph streaming problems. In this paper we give a tight bound on the sketching complexity of counting the number of occurrences of a small subgraph H in a bounded degree graph G presented as a stream of edge updates. Specifically, we show that the space complexity of the problem is governed by the fractional vertex cover number of the graph H. Our subgraph counting algorithm implements a natural vertex sampling approach, with sampling probabilities governed by the vertex cover of H. Our main technical contribution lies in a new set of Fourier analytic tools that we develop to analyze multiplayer communication protocols in the simultaneous communication model, allowing us to prove a tight lower bound. We believe that our techniques are likely to find applications in other settings. Besides giving tight bounds for all graphs H, both our algorithm and lower bounds extend to the hypergraph setting, albeit with some loss in space complexity.

IEEE COMPUTER SOC2018

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or minimize a monotone decreasing supermodular function with a bounded total curvature c. Intuitively, the parameter c represents how nonlinear a function f is: when c = 0, f is linear, while for c = 1, f may be an arbitrary monotone increasing submodular function. For the case of submodular maximization with total curvature c, we obtain a (1 − c/e)-approximation—the first improvement over the greedy algorithm of of Conforti and Cornuéjols from 1984, which holds for a cardinality constraint, as well as a recent analogous result for an arbitrary matroid constraint. Our approach is based on modifications of the continuous greedy algorithm and nonoblivious local search, and allows us to approximately maximize the sum of a nonnegative, monotone increasing submodular function and a (possibly negative) linear function. We show how to reduce both submodular maximization and supermodular minimization to this general problem when the objective function has bounded total curvature. We prove that the approximation results we obtain are the best possible in the value oracle model, even in the case of a cardinality constraint. We define an extension of the notion of curvature to general monotone set functions and show a (1 − c)-approximation for maximization and a 1/(1 − c)-approximation for minimization cases. Finally, we give two concrete applications of our results in the settings of maximum entropy sampling, and the column-subset selection problem.

INFORMS2017

MATH-110(a): Advanced linear algebra I

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et de démontrer rigoureusement les résultats principaux de ce sujet.

MATH-111(f): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.

MATH-111(e): Linear Algebra

L'objectif du cours est d'introduire les notions de base de l'algèbre linéaire et ses applications.