\section*{\sc introduction}
\indent \indent  Ammonia ($NH_{3}$) was discovered in space in 1968 \cite{cheung1968} and its first transition was detected at $23$ $GHz$ with radiotelescope. Ammonia is mostly observed in interstellar medium \cite{ho1983}, and commonly in star forming regions (see e.g. \cite{harju1993}, \cite{jijina1999},
\cite{wienen2012}). However, ammonia is also detected in the cricumstellar envelopes of evolved stars (see, e.g. \cite{schmidt2016} for analysis of ammonia in Asymptotic Giant Branch (AGB) star CW\,Leo).
The Asymptotic Giant Branch stage of stellar evolution
is characteristic for stars with initial mass between 1-8 M$_{\odot}$, that is for stars with low-to-intermediate initial mass, and is characterized by intense mass-loss processes. The AGB stars can be divided into two main types:
C-rich and O-rich ones. The C-rich AGB  stars contain more carbon than oxygen atoms, i.e. C/O > 1. V Cyg itself belongs to this group of objects.
V Cyg is Mira type variable with period of about 417 days, C6 spectral type
\cite{wallerstein1998} and a distance of 420 pc \cite{whitelock2008}. The central star
has low effective temperature (2000-3000K). The star in this phase of evolution has very weak
gravitational force in the stellar atmosphere and changes periodically its radius, temperature and luminosity.
Pulsations are responsible for the dust formation in the outer layers of the atmosphere, and then radiation
pressure on dust can initiate the ejection of material form the atmosphere into space.
Mater ejected from the star forms Circumstellar Envelope (CSE) around the star, where
new molecules, like for example ammonia, are formed. The observed abundance of the NH$_{3}$ is
several magnitudes larger than models of stellar atmosphere for AGB stars predict (e.g. \cite{johnson1982}). The
formation process of ammonia is unknown. The two scenarios have been proposed for ammonia formation in CSE.
In the first scenario ammonia may be formed  by passage of shocks. In this scenario
N$_{2}$ molecules have been dissociated and atoms of nitrogen are available to form the ammonia
molecule \cite{willacy1998}. Unfortunately, the last calculations have been shown that this process change
the abundance of NH$_{3}$ only marginally \cite{gobrecht2016}. The second mechanism is dissociation of N$_{2}$
by the UV radiation because of the CSE is inhomogeneous and the UV radiation may penetrate almost
through the whole envelope \cite{decin2010}.

In Section 2 we present the description of the molecular model of ammonia. The observations and data
reductions are described in Section 3. Section 4 is
devoted to description of modelling process of ammonia lines
in CSE of V\,Cyg. At the last, in Section 5 we discuss
results of our modelling.

\section*{\sc Model of ammonia}

\indent \indent  Ammonia molecule exists in two species: ortho and para. These two species
differ in the orientations of the three hydrogen spins.
Symmetry properties of the ro-vibrational (including inversion) levels are
described by the symmetry group $D_{3h}$ (C$_{3v}$ if the inversion mode is
neglected).
Because of the Pauli exclusion principle, the ro-vibrational levels must belong to
$A'$ and $A"$ (para states) and
$E'$ and $E"$ (ortho states) representations of $D_{3h}$ \cite{bunker2006}.
Ammonia oscillates in six vibrational modes, of which two pairs are
degenerate, and which are described by the four quantum vibrational numbers
($\nu_{1}$, $\nu_{2}$, $\nu_{3}^{l_{3}}$, $\nu_{4}^{l_{4}}$)
and the two vibrational angular momentum l$_3$, and l$_4$.

Ammonia molecule has inversional nature. It is because the potential
energy surface has double minimum corresponding to two positions of the nitrogen atom
on opposite sides of the plane defined by hydrogen atoms. The molecule
may change rapidly its geometry, because its potential barrier between the two minima is small and
equal $2009$ $cm^{-1}$ ($6.4 \times 10^{-14}$ $erg$). In this case energy levels are not
strongly separated and wavefunctions mix together resulting in two kinds of levels: symmetric (s, +) and
antisymmetric (a, -) \cite{bernath2005}.

For calculations of excitation of a molecule in circumstellar envelope one
needs the input file containing the list of adopted energy levels, list of
radiative transitions between energy levels and the set of collisional rates.
For limited number of levels the input file is available in the database
LAMDA (\url{https://home.strw.leidenuniv.nl/~moldata}, \cite{denby1988}, \cite{maret2009}).
Hereby, we followed Schmidt et al. (2016) and the set of levels
extracted from the theoretical EXOMOL database (\url{http://exomol.com},\cite{tennyson2016})
has been used.
The advantage of using computed database instead of laboratory is its completeness.

\section*{\sc Data}

\indent \indent Observations of V Cyg were obtained with the HIFI (\textit{Heterodyne Instrument for the Far Infrared}) instrument on board of the HSO (\textit{Herschel Space Observatory}) in the point mode.
The observations were part of the HIFISTARS Guaranteed Time Key Program (Proposal Id:
KPGT\_vbujarra\_1, PI: V.Bujarrabal). Details of available observations are presented in
Table \ref{tab1}.  For each observations we give spectroscopic designation,
frequency of transition in GHz, band of the HIFI instrument, energy of the upper level in K, observational
identification of, date of observation, the phase of observation, half power beam with (HPBW) of
HIFI instrument, and the main beam efficiency ($\eta_{mb}$) ({Mueller et al.
2014\footnote{\url{http://hertwiki.esac.esa.int/twiki/pub/Public/HifiCalibrationWeb/HifiBeamReleaseNote_Sep2014.pdf}}).
The observational phase of variability was determined relative to the reference data of maximum,
selected from the visual variability curve (see below) ($\phi =$ 0 for Julian Date 2450330), and assuming
variability period of 417 days \cite{samus2009}).
Only the ground rotational transition of ortho-NH$_{3}$ was recorded in two instrumental settings
observed at the same time.
The reduction of data was conducted using HIPE (v.15.0.1)
software\footnote{\url{https://www.cosmos.esa.int/web/herschel/hipe-download}}.
The reduction process was limited
to extraction of data from level 2, tracing continuum and removing baseline, averaging of two H and V
polarizations, and final averaging of two settings. For comparison with theoretical models, the antenna
temperature was converted to the main beam temperature using main beam coefficients. The final
profile of the 1$_{0}$-0$_{0}$ ortho-ammonia line is shown in Figure~\ref{fig1}
on a Doppler velocity scale relative to the Local Standard of Rest V$_{LSR}$.
The root mean square (r.m.s.) in the continuum amounts to 3~mK.
The uncertainty of the flux is expected to be less than 10 percent \cite{roelfsema2012}.

For the analysis of variability we used data available in AAVSO database\footnote{https://www.aavso.org/}.
AAVSO database provides a very long sequence of photometric observations in visual covering
both HIFI and ISO periods of observations. Sequence of data covering ISO observations is shown in
Figure~\ref{fig2}.

The main source of data for the Spectral Energy Distribution (SED) modelling is atlas of
ISO (Infrared Space Observatory)
observations available on \url{https://users.physics.unc.edu/~gcsloan/library/swsatlas/aot1.html}
(\cite{kraemer2002}, \cite{sloan2003}). This catalogue includes 1239 full-scan AOT1 spectra from
Short Wavelength Spectrometer (SWS). These spectra contain photometric scan between about 2.4 to
45.4 $\mu$m for each object. All spectra were reduced and ready to use for modelling \cite{sloan2003}.
In collection of spectra we found six spectral scans of our object (Table \ref{tab2}).
One spectral scan was observed at variability phase close to that of HIFI observations (ID = 69500110)
and was used for modelling of the SED (Figure \ref{fig3}).
Photometry was updated with photometrical measurements  of V\footnote{\url{http://simbad.u-strasbg.fr/simbad/sim-ref?querymethod=bib&simbo=on&submit=submit+bibcode&bibcode=2002yCat.2237....0D}},
J, H and K bands (\cite{cutri2003}, date of observation: 2000-05-04, JD date: 2451668.9397,
    phase: $\phi=$ 0.2)\footnote{\url{http://vizier.u-strasbg.fr/viz-bin/VizieR?-source=II/246}} and
with IRAS measurements for 12, 25, 60 and 100 $\mu$m\footnote{\url{http://vizier.u-strasbg.fr/viz-bin/VizieR-5?-out.add=.&-source=II/125/main,II/126/sources&IRAS==20396\%2b4757\%2a}}
(in this case the flux reported in the catalogue
is average value of the IRAS observations at each band, and the phase is unknown
\footnote{https://lambda.gsfc.nasa.gov/product/iras/colorcorr.cfm}).

\begin{table}
 \centering
 \caption{The characteristics of HIFI/\textit{Herschel} observations.}\label{tab1}
 \vspace*{1ex}
 \begin{tabular}{ccccccccc}
  \hline
  Transition & Frequency & Band & E$_{u}$ & \textit{Herschel} & Obs. date & Phase & HPBW & $\eta_{mb}$ \\
            & (GHz)      &      & (K)     & OBSID             &           &       &      &             \\
  \hline
  1$_{0}$(s) - 0$_{0}$(a) & 572.498 & 1b & 29 & 1342199153 & 2010-23-06  & 0.1  & 37.5" & 0.62 \\
                          &         &    &    & 1342199154 & 2010-23-06  & 0.1  & 37.5" & 0.62 \\
 \hline
 \end{tabular}
\end{table}

\begin{table}
 \centering
 \caption{The parameters of the ISO SWS for V Cyg.}\label{tab2}
 \vspace*{1ex}
 \begin{tabular}{ccccc}
  \hline
  Source name & ID & Date & Time of observation (s) & Phase \\
  \hline
  V Cyg & 08001855 & 1996-05-02 & 1044 & 0.49\\
        & 42100111 & 1997-10-01 & 1912 & 0.31\\
        & 42300307 & 1997-12-01 & 1913 & 0.31\\
        & 51401308 & 1997-13-04 & 1912 & 0.53\\
        & 59501909 & 1997-03-07 & 1912 & 0.73\\
        & 69500110 & 1997-10-10 & 1912 & 0.99\\
 \hline
 \end{tabular}
\end{table}

\section*{\sc Modelling}

\indent \indent The first step in modelling was preparation of the model of the dusty envelope of V~Cyg.
For that purpose, we used MRT code for a dust radiative transfer \cite{szczerba1997}.
In SED modelling we assumed that the amplitude of luminosity variation is
about 40 \%
relative to the average value deduced
from the period-luminosity relation \cite{whitelock2008}
of 6600 L$_{\odot}$.
Such an amplitude was deduced for the similar case for the best examined C-rich
star - CW Leo \cite{menshchikov2001}. Hence, in the phase of maximum the obtained luminosity
equals 9200 L$_{\odot}$.
The optimal model of the dusty envelope reproduces well observed SED for V Cyg both in the maximum phase
(presented on Figure~\ref{fig1}) and in the minimum phase. The adopted parameters of the central source
and of the dust are presented in Table~\ref{tab3}.

\begin{table}[H]
 \centering
 \caption{The parameters for model of V Cyg.}\label{tab3}
 \vspace*{1ex}
 \begin{tabular}{cccc}
  \hline
  \hline
  RA (2000)     & 20 41 18.27                                      & Luminosity (mean) & 6600$^2$ L$_{\odot}$\\
  Dec (2000)    & +48 08 28.94                                     & Luminosity (max)  & 9200$^4$ L$_{\odot}$\\
  Period        & 417 days$^1$                                     & Luminosity (min)  & 4000$^4$ L$_{\odot}$\\
  Distance      & 420 pc$^2$                                       & T$_{eff, max}$    & 2500$^4$ K\\
  V$_{exp}$     & 11.5 km s$^{-1}$ $^3$                            & T$_{eff, min}$    & 2000$^4$ K\\
  V$_{LSR}$     & 13.5 km s$^{-1}$ $^6$                            & f(ortho-NH$_{3}$) & 3.3 $\times$ 10$^{-6}$ $^4$\\
  R$_{phot}$    & 1.5 $\times$ 10$^{16}$ cm                        & f(NH$_{3}$)       & 6.6 $\times$ 10$^{-6}$ $^4$\\
  M$_{loss}$    & 1.7 $\times$ 10$^{-6}$ M$_\odot$ yr$^{-1}$ $^5$  &                   & \\
 \hline
 \hline
 \end{tabular}
 \\$^1$ \cite{samus2009}, $^2$ \cite{whitelock2008}, $^3$ Derivatives from CO lines, $^4$ SED modelling,
 $^5$\cite{shoier2013}, $^6$ \cite{massalkhi2018}
\end{table}

The optical properties of the dust
obtained
from the
SED
modelling were used to calculate the
photodissociation radius of ammonia. For that purpose, we used CSENV (\textit{CircumStellar ENVelopes})
code for the calculations of chemistry in expanding envelope \cite{glassgold1986}. The chemical contents
of the input was restricted to ammonia and products of its photodissociation.
The photodissociation radius, R$_{ph}$ is defined as the radius at which the initial
abundance of ammonia drops twice. In our calculations we have used the latest cross-section rates of ammonia
molecules \cite{heays2017}.
In case of V~Cyg we obtained value of 1.5 $\times$ 10$^{16}$ cm (for the mass loss
rate $\dot{M} =$ 1.7 $\times$ 10$^{-6}$ M$_{\odot}$ yr$^{-1}$ and expansion velocity V$_{exp} =$ 11.5 km
s$^{-1}$). Applying the same approach to analysed earlier CW Leo \cite{schmidt2016}, we found
theoretical R$_{ph}$ equal to 4 $\times$ 10$^{16}$ cm,
close to the value
obtained observationally
of 3.5 $\times$ 10$^{16}$ cm for the rotational transitions of ortho-NH$_{3}$ (2.0 $\times$ 10$^{16}$ cm
suggested by inversional transitions). We estimate that the uncertainty of the theoretical value
may be of factor 2.

For modelling of ammonia lines we used a radiative transfer code MOLEXCSE (\textit{Molecular Line EXcitation in CircumStelar Envelope}) code. This code solves the non-LTE radiative transfer in molecular lines
in presence of the continuum. The code reproduces well flux in continuum for the absorption, scattering and emissivity provided by MRT code.
The density structure of the gas envelope is determined by the assumed mass loss rate and constant expansion velocity.
The gas kinetic temperature distribution in the envelope of V~Cyg was
determined by finding the best fit to CO emission lines including both radio,
milimeter and sub-milimeter HIFI transitions (\cite{neufeld2010}).

The model of ortho-ammonia molecule includes 172 levels (all the ground vibrational
and the first excited bending mode $\nu_2$=1 levels with J $=<$ 15),
1579 radiative transitions and collisional excitation by H$_{2}$. For the details of
treatment of collisional rates see \cite{schmidt2016}.
Inclusion of the rovibrational transitions (about 10 $\mu$m) is of key importance
for the proper modelling of excitation of ammonia in circumstellar envelope
(see e.g. \cite{schmidt2016}).

\begin{figure}[!h]
\centering
\begin{minipage}[t]{.45\linewidth}
\centering
\epsfig{file = VCyg_nh3_572_v3.png,width = .99\linewidth}
\caption{
The averaged line profile of NH$_{3}$ obtained from HIFI/\textit{Herschel}
observations.
The black solid line shows the brightness for the model of ammonia in maximum phase of variability of VCyg,
the black dashed line - in minimum phase of variability. The vertical arrow indicates
the LSR velocity of the source\cite{massalkhi2018}.}\label{fig1}
\end{minipage}
\hfill
\begin{minipage}[t]{.45\linewidth}
\centering
\epsfig{file = vis_vs_infrared.png,width = .99\linewidth}
\caption{Variability of V~Cyg. The upper diagram shows the measurements flux at 10 $\mu$m from
ISO observations (triangle points) and fit sine function to show how flux
changed with the period of variability. The bottom diagram presents AAVSO data (circle points,
visual observations, AAVSO (American Association of Variable Stars Observers)),
and determinations of period
(solid line). The broken vertical line
presents positions of the ISO observations for V Cyg. The shift between
amplitude of this two sets of data is equal about 0.07.}\label{fig2}
\end{minipage}
\end{figure}

\begin{figure}[!h]
\centering
\begin{minipage}[t]{.45\linewidth}
\centering
\epsfig{file = VCyg_article_max.png,width = .99\linewidth}
\caption{
The SED (\textit{Spectral Energy Distribution}).
Triangle points shows measurements flux for V, J, H and K bands,
square points
- IRAS measurements for 12, 25, 60 and 100 $\mu$m, the solid line - ISO
measurements between 2.36 - 45.365 $\mu$m (ID: 69500110, phase: $\phi =$ 0.99).
The
dashed line shows model of SED.}\label{fig3}
\end{minipage}
\hfill
\begin{minipage}[t]{.45\linewidth}
\centering
\epsfig{file = vcyg_distribution.png,width = .99\linewidth}
\caption{
The distribution of NH$_{3}$ molecule in CSE around V Cyg.
This model was been calculated by CSENV code \cite{glassgold1986}. This distribution
have been calculated for the model of dust obtain for our SED model and the latest
cross-section of ammonia molecule \cite{heays2017}.}\label{fig4}
\end{minipage}
\end{figure}

\section*{\sc Result and conclusion}

For adopted parameters the abundance of ortho-NH$_{3}$ molecules in V~Cyg star in
maximum phase which reproduces at best observed line profile amounts to
3.3 $\times$ 10$^{-7}$ relative to the molecular hydrogen.
The resulting theoretical profile is shown on Figure~\ref{fig3} with the black line.
The computed profile seems to reproduce very well almost flat top shape of the observed transition.

To illustrate expected variability in line profile, we computed the theoretical profile
of 1$_{0}$-0$_{0}$ transition also
from the minimum phase, using abundance determination
in the maximum phase. The resulting profile is presented on Figure~\ref{fig3} by means of the dotted line.
In that case we used ISO data in the minimum phase (ID: 08001855, phase: $\phi =$ 0.49).
For the model of the SED in the phase of minimum, we adopted central star luminosity to be equal 4000
L$_{\odot}$ and the temperature to be 2000 K.
The brightness of the 572.498 GHz line is then reduced by 40~\% relative to its
maximum.

No observations of para-ammonia are available for V~Cyg. If ortho-to-para ratio corresponds to
the equilibrium conditions at higher temperatures, i.e. it is equal to one, then the total amount of ammonia
in the envelope of V~Cyg is 6.6 $\times$ 10$^{-7}$. The abundance of ammonia in the archetypical
C-rich AGB star IRC+10216 amounts 6 $\times$ 10$^{-8}$ \cite{schmidt2016} for the adopted there mass loss rate of 3.25 $\times$ 10$^{-5}$ M$_{\odot}$ yr$^{-1}$. Thus, within uncertainties one may conclude that
mass production rate of ammonia in envelopes of both objects is similar despite significantly different
gas densities. If photochemical reactions would be responsible for the production of ammonia
in the envelopes of C-rich AGB stars, then higher abundance of ammonia in V~Cyg could be explained
by the higher probability that UV photons may penetrate into inner parts of the envelope while its density is smaller. The analysis of other 6 objects in the sample, now under consideration, will reveal if that expectations will be confirmed.

\section*{\sc acknowledgement}
\indent \indent
We acknowledge support from the grant 2016/21/B/ST09/01626
of the National Science Centre, Poland.


\section{Introduction}\label{intro}

Rego and Kirczenow \cite{PhysRevLett.81.232.1998.Rego} and, independently, Angelescu, Cross, and Roukes \cite{SuperlatticesMicrostructures23.673.1998.Angelescu}, proved theoretically that the phonons heat conductance, $\kappa$, of a quasi one-dimensional dielectric wire in the ballistic regime in the low temperature limit, is quantized in units of
\begin{equation}
  \kappa_0\equiv\frac{\pi^2k_B^2T}{3h}, \label{kappa_LT}
\end{equation}
namely $\kappa = {\mathcal N}_c\kappa_0$, where ${\mathcal N}_c$ is the number of phonon channels available along the wire, $h$ is the Plank constant and $k_B$ is the Boltzmann constant and $T$ is the average temperature between the ends 1 and 2 of the wire, $T=(T_1+T_2)/2$, assuming that $|T_1-T_2|/T\ll 1$.

These results have been experimentally confirmed in Refs. \cite{Nature404.974.2000.Schwab,Nature.444.187.2006.Meschke} and have been extended by Rego and Kirczenow in Ref. \cite{PhysRevB.59.13080.1999.Rego}, where they showed that the same quantization rule applies to the heat conductance of particles of any statistics.

Let us consider a two-terminal transport experiment in which the reservoirs 1 and 2 are connected by a quasi 1D wire. The temperatures and chemical potentials in the two reservoirs will be denoted by $T_{i}$ and $\mu_{i}$, respectively ($i=1,2$). The particles in the system may be bosons, fermions, or may obey fractional exclusion statistics (FES) of parameter $\alpha$ \cite{PhysRevLett.67.937.1991.Haldane,PhysRevLett.73.922.1994.Wu,PhysRevLett.104.198901.2010.Anghel,PhysRevLett.104.198902.2010.Wu,EPL.87.60009.2009.Anghel}. Then the Landauer formula for the particle and heat fluxes between the two reservoirs are \cite{PhysRevB.59.13080.1999.Rego,PhysRep.395.159.2004.Blencowe}
\begin{subequations}\label{IUgen}
\begin{eqnarray}
  I &=& \sum _{n=1}^{{\mathcal N}_c}\int_{0}^{\infty}\frac{dk}{2\pi}v_{n}(k)\left[\eta_{1}(k)-\eta_{2}(k)\right]\zeta_n(k)
  \label{Igen} \\
  \dot U &=& \sum _{n=1}^{{\mathcal N}_c}\int_{0}^{\infty}\frac{dk}{2\pi}\epsilon v_{n}(k)\left[\eta_{1}(k)-\eta_{2}(k)\right]\zeta_n(k)
  \label{Ugen}
\end{eqnarray}
\end{subequations}
where $v_{n}(k)$ is the group velocity of the particles of momentum $k$, $\eta_{i}(k)$ denotes the thermal particle population in the reservoir $i$ and, finally, $\zeta_n(k)$ is the particle transmission coefficient through the wire. The summation is taken over the 1D (available) channels along the wire.

Since the particle group velocity is $v_{n}(k)=\hbar^{-1}(d\epsilon(k)/dk)$, and assuming further that $\zeta_n(k)\equiv\zeta_n$ is independent of $k$, Eqs. (\ref{IUgen}) get the simple form
\begin{subequations}\label{IUgen1}
\begin{eqnarray}
  I &=& \frac{\zeta_n}{h}\sum _{n=1}^{{\mathcal N}_c}\int_{\epsilon_n(0)}^{\infty}d\epsilon\left[\eta_{1}(\epsilon)-\eta_{2}(\epsilon)\right]
  \label{Igen1} \\
  \dot U &=& \frac{\zeta_n}{h}\sum _{n=1}^{{\mathcal N}_c}\int_{\epsilon_n(0)}^{\infty}d\epsilon\,\epsilon\left[\eta_{1}(\epsilon)-\eta_{2}(\epsilon)\right]
  \label{Ugen1}
\end{eqnarray}
\end{subequations}
where $\epsilon_n(0)$ is the lowest energy level in the channel $n$.

To calculate the heat conductivity, $\kappa\equiv\dot U/(T_1-T_2)$, one introduces in (\ref{IUgen1}) the FES populations \cite{PhysRevB.59.13080.1999.Rego,PhysRevLett.73.922.1994.Wu,EPL.90.10006.2010.Anghel},
\begin{subequations}\label{EqFES}
\begin{eqnarray}
  &&\eta_{i}(\epsilon)\equiv\eta_\alpha(\epsilon,\mu,T) = \left[w_\alpha(\mu,T)+\alpha\right], \label{Eq_eta} \\
  &&w_\alpha^{\alpha}(\mu,T)[1+w_\alpha(\mu,T)]^{1-\alpha}=\exp[\beta(\epsilon-\mu)], \label{Eq_w}
\end{eqnarray}
\end{subequations}
where $\beta\equiv 1/(k_BT)$ ($\alpha=0$ and 1 correspond to bosons and fermions, respectively). By doing so, Rego and Kirczenow calculated the low temperature limit of $\kappa$ and observed that it is independent of $\alpha$ and therefore the quantization relation (\ref{kappa_LT}) holds for particles of any statistics \cite{PhysRevB.59.13080.1999.Rego,PhysRep.395.159.2004.Blencowe}. Nevertheless, a physical understanding of this mathematical result is still missing \cite{PhysRep.395.159.2004.Blencowe}.

In this letter I extend the results of Rego and Kirczenow by showing that the heat conductivity of a 1D channel is independent of the statistics of particles at any temperature and I will provide a microscopic explanation for this result. This is done by observing that there is a close similarity between the stationary heat and particle transport in 1D and equilibrium thermodynamics in 2D (or, in systems with constant single-particle density of states, DOS \cite{ProcCambrPhilos42.272.1946.Auluc,PhysRev.135.A1515.1964.May,PhysRevE.55.1518.1997.Lee,PhysA304.421.2002.Lee,JPA35.7255.2002.Anghel,RJP.54.281.2009.Anghel,JPA38.9405.2005.Anghel}). The quanta of heat conductance is then nothing but the low temperature limit of the 1D heat conductance. Moreover, I calculate the entropy current through the channel and I show that this is also independent of statistics at any temperature as long as the particle current is zero.

Let us focus on systems with only one channel, $n$. We split the particle and heat fluxes into two parts, one coming from the reservoir 1 and one from the reservoir 2, $I_n\equiv I_{n,1}(\mu_1,T_1)-I_{n,1}(\mu_2,T_2)$ and $\dot U_n\equiv\dot U_{n,1}(\mu_1,T_1)-\dot U_{n,1}(\mu_2,T_2)$, where
\begin{subequations}\label{IUnsplit}
\begin{eqnarray}
  I_{n,1}(\mu_n,T_n) &\equiv& \frac{\zeta_n}{h}\int_{\epsilon_n(0)}^{\infty}\eta_{\alpha}(\epsilon,\mu_n,T_n)d\epsilon \label{Insplit} \\
  \dot U_{n,1}(\mu_n,T_n) &\equiv& \frac{\zeta_n}{h}\int_{\epsilon_n(0)}^{\infty}\epsilon\eta_{\alpha}(\epsilon,\mu_n,T_n)d\epsilon
  \label{Unsplit}
\end{eqnarray}
\end{subequations}
We observe that $I_{n,1}(\mu_n,T_n)$ and $\dot U_{n,1}(\mu_n,T_n)$ have exactly the same expressions as the particle number, $N_\alpha(\mu_n,T_n)$, and internal energy, $U_\alpha(\mu_n,T_n)$, respectively, of a FES system of parameter $\alpha$ in equilibrium at temperature $T$ and chemical potential $\mu$, which has a constant DOS, $\sigma=\zeta_n/h$. Therefore we can apply here directly the results we obtained for these latter systems in Ref. \cite{JPA35.7255.2002.Anghel}. To specify the notations, let us briefly review the results of Ref. \cite{JPA35.7255.2002.Anghel} which are of interest here.

If a FES system of parameter $\alpha$ and density of states $\sigma=\zeta_n/h$, in equilibrium at temperature $T$, contains $N_\alpha$ particles, then we define the statistics independent parameter $y_0$ by the relation
\begin{subequations}\label{def_N_y0_mu}
\begin{equation}
  N_\alpha \equiv k_BT\sigma\log(1+y_0). \label{N}
\end{equation}
Knowing $y_0$, one may calculate the chemical potential, $\mu$, from the equation
\begin{equation}
  (1+y_0)^{1-\alpha}/y_0 = e^{-\beta\mu}  \label{defy0}
\end{equation}
and from Eqs. (\ref{N}) and (\ref{defy0}) we observe that
\begin{equation}\label{mu}
\exp{[(\mu - \alpha N_\alpha/\sigma)/k_{\rm B} T]} = 1- \exp{[-N_\alpha/(\sigma k_{\rm B}T)]}.
\end{equation}
\end{subequations}
If we identify the (generalized) Fermi energy as $\epsilon_{\rm F}\equiv\lim_{T\to 0}\mu = \alpha N_\alpha/\sigma$ we observe that $\mu-\epsilon_{\rm F}$ is also independent of $\alpha$, or, \textit{vice-versa}, $\mu-\epsilon_{\rm F}$ determine uniquely $N_\alpha$, for any $\alpha$.

In these notations, the grandcanonical potential and internal energy, $\Omega_\alpha$ and $U_\alpha$ are \cite{JPA35.7255.2002.Anghel}
\begin{eqnarray}\label{echiv}
\Omega_\alpha = -U_\alpha &=& (k_{\rm B}T)^2 \sigma\left[\frac{1-\alpha}{2}
\log^2{(1+y_0)} + Li_2(-y_0)\right] \nonumber \\
&& = \frac{1-\alpha}{2}\frac{N_\alpha^2}{\sigma} + (k_{\rm B} T)^2 \sigma Li_2(-y_0) ,
\end{eqnarray}
where $Li_2$ is the Euler's dilogarithm, $Li_2(z) = \sum_{i=1}^{\infty}z^k/k^2$ \cite{Lewin:book}.
The fact that, at constant $N_\alpha$, the temperature dependent part of $\Omega_\alpha$ and $U_\alpha$, i.e. $(k_{\rm B} T)^2\sigma Li_2(-y_0)$, is independent of $\alpha$ is an expression of the thermodynamic equivalence of quantum gases of the same, constant DOS \cite{ProcCambrPhilos42.272.1946.Auluc,PhysRev.135.A1515.1964.May,PhysRevE.55.1518.1997.Lee,PhysA304.421.2002.Lee,JPA35.7255.2002.Anghel}.

From Eqs. (\ref{echiv}) and (\ref{N}), one can obtain the entropy and the heat capacity \cite{JPA35.7255.2002.Anghel},
\begin{eqnarray}
S
&=& -k_{\rm B}^2 T \sigma [2Li_2(-y_0) + \log{(1+y_0)}\log{y_0}]
\label{entropia} \\
C_{\rm V}
&=& - \frac{N_\alpha^2}{T\sigma}\frac{1+y_0}{y_0}- 2k_{\rm B}^2
T\sigma Li_2(-y_0) , \label{cv}
\end{eqnarray}
which are both independent of $\alpha$. Since, according to Eq. (\ref{N}), $\lim_{T\to0}y_0=\infty$, using the asymptotic behavior of the dilogarithm, $Li_2(-y_0) \sim -[\pi^2/6 + \log^2(y_0)/2]$, one can recover in the low temperature limit the universal asymptotic expression for the heat capacity of the system, namely \cite{Stone:book}
\begin{equation}
  C_V\sim(\pi^2/3)k_B^2T\sigma. \label{cv_limT0}
\end{equation}

Now we have all the ingredients and we can transcribe the formalism above into a formalism for the particle and heat transport along the wire. For this, we identify $I_{n,1}(\mu_n,T_n)$ with $N_\alpha(\mu_n,T_n)$, and we introduce $y_{i0}$ by
\begin{subequations}\label{IUpoly}
\begin{eqnarray}
  &&I_{n,1}(\mu_n,T_n) \equiv \frac{\zeta_nk_BT_n}{h}\log(1+y_{i0}), \label{In} \\
  && (1+y_{i0})^{1-\alpha}/y_{i0} = e^{-\beta_n\mu_n},  \label{yin}
\end{eqnarray}
\begin{equation}
  \exp{[(\mu - \alpha h I_{n,1}/\zeta_n)/k_{B} T_n]} = 1- \exp{[-hI_{n,1}/(\zeta_n k_{B}T_n)]},  \label{muI}
\end{equation}
in analogy to Eqs. (\ref{def_N_y0_mu})

From the equations above and observing that $\dot U_{n,1}(\mu_n,T_n)$ has an expression similar to that of $U_\alpha(\mu_n,T_n)$, we obtain
\begin{eqnarray}
\dot U_{n,1}
  &=& -\frac{1-\alpha}{2}\frac{hI_{n,i}^2}{\zeta_n} - (k_{\rm B} T_n)^2 \frac{\zeta_n}{h} Li_2(-y_{i0}) .\label{dotUechiv2}
\end{eqnarray}
\end{subequations}
From Eqs. (\ref{IUpoly}) we calculate
\begin{subequations} \label{dIdTdmu}
\begin{eqnarray}
  \frac{\partial I_{n,1}}{\partial T} &=& \frac{I_{n,1}}{T}-\frac{\zeta_n\mu}{hT}\frac{1-\exp\left[-\frac{hI_{n,1}}{\zeta_n k_BT}\right]}{\alpha+(1-\alpha)\exp\left[-\frac{hI_{n,1}}{\zeta_n k_BT}\right]} \nonumber \\
  &=& \frac{\zeta_n k_B}{h}\log(1+y_{i0}) - \frac{\zeta_n\mu}{hT}\frac{y_{i0}}{1+\alpha y_{i0}}, \label{dIdT}
\end{eqnarray}
\begin{equation}
  \frac{\partial I_{n,1}}{\partial \mu} = \frac{\frac{\zeta_n}{h}\left[1-\exp\left(-\frac{hI_{n,1}}{\zeta_n k_BT}\right)\right]}{\alpha+(1-\alpha)\exp\left(-\frac{hI_{n,1}}{\zeta_n k_BT}\right)}
  = \frac{\zeta_n y_{i0}}{h(1+\alpha y_{i0})}.
  \label{dIdmu}
\end{equation}
\end{subequations}
\begin{subequations} \label{ddotUdTdmu}
\begin{eqnarray}
\frac{\partial \dot U_{n,1}}{\partial T} &=& -(1-\alpha)\frac{hI_{n,1}}{\zeta_n}\frac{\partial I_{n,1}}{\partial T} - 2k_{\rm B}^2 T_n \frac{\zeta_n}{h} Li_2(-y_{i0}) \nonumber \\
&& + \frac{\mu I_{n,1}(1+y_{i0})}{T(1+\alpha y_{i0})}, \label{ddotUdT}
\\
\frac{\partial \dot U_{n,1}}{\partial\mu} &=&-(1-\alpha)\frac{hI_{n,1}}{\zeta_n}\frac{\partial I_{n,1}}{\partial\mu} - 2k_{\rm B}^2 T_n \frac{\zeta_n}{h} Li_2(-y_{i0}) \nonumber \\
&& + \frac{I_{n,1}(1+y_{i0})}{1+\alpha y_{i0}}, \label{ddotUdmu}
\end{eqnarray}
\end{subequations}

To calculate the low temperature approximations, we use the fact that $\lim_{T\to0}y_{i0}=\infty$ for any $\alpha$ and obtain
\begin{subequations}\label{lowTexpr1}
\begin{eqnarray}
  y_{i0,\alpha>0} &\stackrel{T\to0}{\sim}& e^{\frac{\mu}{\alpha k_BT}}+\frac{1-\alpha}{\alpha},\label{lowTy0} \\
  I_{n,1,\alpha>0} &\stackrel{T\to0}{\sim}& \frac{\zeta_n\mu}{h\alpha} + \frac{(1-\alpha)\zeta_n k_BT}{\alpha h}e^{-\frac{\mu}{\alpha k_BT}} \label{lowTI} \\
  \dot U_{n,1,\alpha>0} &\stackrel{T\to0}{\sim}& \frac{\zeta_n\mu^2}{2h\alpha} +\frac{\pi^2\zeta_n(k_BT)^2}{6h} +\frac{(1-\alpha)\zeta_nk_BT\mu}{\alpha h}
  \nonumber \\
  && \times e^{-\frac{\mu}{\alpha k_BT}} \label{lowTdotU}
\end{eqnarray}
for $\alpha>0$, whereas for $\alpha=0$ we have
\begin{eqnarray}
  y_{i0,\alpha=0} &\stackrel{T\to0}{\sim}& -\frac{k_BT}{\mu}-\frac{1}{2},\label{lowTy0a0} \\
  I_{n,1,\alpha=0} &\stackrel{T\to0}{\sim}& -\frac{\zeta_nk_BT}{h}\left[\log\left(-\frac{\mu}{k_BT}\right)+\frac{\mu}{2k_BT}\right] \label{lowTIa0} \\
  \dot U_{n,1,\alpha=0} &\stackrel{T\to0}{\sim}& \frac{\pi^2\zeta_n(k_BT)^2}{6h} -\frac{\zeta_nk_BT\mu}{h}\log\left[-\frac{\mu}{k_BT}\right] \label{lowTdotUa0}
\end{eqnarray}
\end{subequations}

From Eqs. (\ref{lowTexpr1}) we calculate the derivatives of $I_{n,1}$ and $\dot U_{n,1}$ at low temperatures:
\begin{subequations}\label{lowTderivs}
  \begin{eqnarray}
    \frac{\partial I_{n,1,\alpha>0}}{\partial T} &\stackrel{T\to0}{\sim}& \frac{(1-\alpha)\zeta_nk_B}{\alpha h}\left[\frac{\mu}{\alpha k_BT}+1\right]e^{-\frac{\mu}{\alpha k_BT}} \label{lowTdIpdtT0} \\
    %
    \frac{\partial I_{n,1,\alpha>0}}{\partial\mu} &\stackrel{T\to0}{\sim}& \frac{\zeta_n}{h\alpha} - \frac{(1-\alpha)\zeta_n}{\alpha^{2} h}e^{-\frac{\mu}{\alpha k_BT}}  \label{lowTdIpdmuT0} \\
    %
    \frac{\partial \dot U_{n,1,\alpha>0}}{\partial T} &\stackrel{T\to0}{\sim}& \frac{\pi^2\zeta_nk_B^2T}{3h} +\frac{(1-\alpha)\zeta_nk_BT\mu}{\alpha h} \nonumber \\
    && + \frac{(1-\alpha)\zeta_nk_B\mu}{\alpha h}\left[\frac{\mu}{\alpha k_BT}+1\right]e^{-\frac{\mu}{\alpha k_BT}} \label{lowTddotUpdtT0} \\
    %
    \frac{\partial \dot U_{n,1,\alpha>0}}{\partial \mu} &\stackrel{T\to0}{\sim}& \frac{\zeta_n\mu}{h\alpha} -\frac{(1-\alpha)\zeta_nk_BT}{\alpha h}\left[\frac{\mu}{\alpha k_BT}-1\right] \nonumber \\
    && \times e^{-\frac{\mu}{\alpha k_BT}} \label{lowTddotUpdmuT0}\\

    \frac{\partial I_{n,1,\alpha=0}}{\partial T} &\stackrel{T\to0}{\sim}& \frac{\zeta_nk_B}{\alpha h}\left[-\log\left(-\frac{\mu}{\alpha k_BT}\right)+1\right] \label{lowTdIpdta0} \\
    %
    \frac{\partial I_{n,1,\alpha=0}}{\partial\mu} &\stackrel{T\to0}{\sim}& -\frac{\zeta_n k_BT}{h\mu}\left(1+\frac{\mu}{2 k_BT}\right) \label{lowTdIpdmuT0a0} \\
    %
    \frac{\partial \dot U_{n,1,\alpha=0}}{\partial T} &\stackrel{T\to0}{\sim}& \frac{\pi^2\zeta_nk_B^2T}{3h} +\frac{\zeta_nk_B^2T}{h}\frac{\mu}{k_BT} \nonumber \\
    && \times\left[-\log\left(-\frac{\mu}{k_BT}\right)-1\right] \label{lowTddotUpdta0} \\
    %
    \frac{\partial \dot U_{n,1,\alpha=0}}{\partial \mu} &\stackrel{T\to0}{\sim}& \frac{\zeta_nk_BT}{h}\left[-\log\left(-\frac{\mu}{k_BT}\right)-1\right] \label{lowTddotUpdmua0}
  \end{eqnarray}
\end{subequations}
We observe that the results (\ref{lowTderivs}) for $\alpha>0$ coincide  in the lowest order approximation with the results (16)-(19) of Ref. \cite{PhysRevB.59.13080.1999.Rego}, but they are different in general for $\alpha=0$. For example $\lim_{T\to0}\partial I_{n,1}/\partial T=\infty$ for $\alpha=0$, whereas for $\alpha>0$ $\lim_{T\to0}\partial I_{n,1}/\partial T=0$. The only result that remains the same in the lowest order approximation for both, $\alpha>0$ and $\alpha=0$, is $\partial\dot U_{n,1}/\partial T=\zeta_n\pi^2k_B^2T/(3h)$, which is the quanta of heat conductance if we set $\zeta_n=1$.

Nevertheless, in real heat conductance measurements the heat transport takes place without particle transport. Therefore the derivative $(\partial\dot U_{n,1}/\partial T)_\mu$ (taken at constant $\mu$) is not the quantity of interest for us. The quantity which represents the heat conductivity is actually $(d\dot{U}_{n,1}/dT)_{I_{n}=0}\equiv(d\dot{U}_{n,1}/dT)_{I_{n,1}}$, which is the derivative of $\dot U_{n,1}$ with respect to $T$, at constant $I_{n,1}(\mu,T)$. In these conditions the variations of $T$ and $\mu$ between the two reservoirs are related by
\begin{equation}
  \left.\frac{d\mu}{dT}\right|_{I_{n,1}} = -\left.\frac{\partial I_{n,1}}{\partial T}\right|_{\mu}\left(\left.\frac{\partial I_{n,1}}{\partial \mu}\right|_{T}\right)^{-1}. \label{dmudT_I}
\end{equation}
Plugging Eq. (\ref{dmudT_I}) into the expression for $(d\dot U_{n,1}/dT)_{I_{n,1}}$, we obtain
\begin{equation}
  \kappa=\left.\frac{d\dot U_{n,1}}{dT}\right|_{I_{n,1}} = \frac{\partial\dot U_{n,1}}{\partial T}-\frac{\partial\dot U_{n,1}}{\partial \mu}\left.\frac{\partial I_{n,1}}{\partial T}\right|_{\mu}\left(\left.\frac{\partial I_{n,1}}{\partial \mu}\right|_{T}\right)^{-1} \label{kappa_gen}
\end{equation}
which, if we replace $I_{n,1}$ by $N_\alpha$ and $\dot U_{n,1}$ by $U_\alpha$, becomes identical to the expression for the heat capacity, $C_V$ (\ref{cv}). Therefore we can transcribe Eq. (\ref{cv}) for the heat conductivity as
\begin{equation}
  \kappa_{n} = - \frac{I_{n,1}^2}{T\sigma}\frac{1+y_{i,0}}{y_{i,0}}-2k_{\rm B}^2T\sigma Li_2(-y_{i,0}) , \label{kappa_univ}
\end{equation}
which is independent of $\alpha$ at any temperature. In the low temperature limit Eq. (\ref{kappa_univ}) becomes the universal asymptotic expression, $\kappa_0$ (\ref{kappa_LT}), which is equivalent to (\ref{cv_limT0}) from equilibrium thermodynamics.

The result (\ref{kappa_LT}) was obtained before \cite{PhysRevLett.81.232.1998.Rego,SuperlatticesMicrostructures23.673.1998.Angelescu,PhysRevB.59.13080.1999.Rego,PhysRep.395.159.2004.Blencowe} without imposing the condition $dI_{n,1}=0$ due to the fact that the second term at the right hand side of Eq. (\ref{kappa_gen}) converges to zero at $T\to0$, as one can readily check from the asymptotic expressions (\ref{lowTderivs}).

In Ref. \cite{PhysRep.395.159.2004.Blencowe} Blencowe analyzed also the entropy flux through the 1D channel in the low temperature limit and observed that it is independent of $\alpha$. Let's analyze it here from the perspective of Ref. \cite{JPA35.7255.2002.Anghel} and prove that it is independent of $\alpha$ at any temperature.

The entropy flux from one of the reservoirs may be calculated in a way similar to the calculation of heat and particle fluxes:
\begin{eqnarray}
  \dot S &=& \frac{k_B\zeta_n}{h}\int_{0}^{\infty}\big\{[1+(1-\alpha)n(\epsilon)]\log[1+(1-\alpha)n(\epsilon)]\nonumber \\
  && -n(\epsilon)\log[n(\epsilon)]-[1-\alpha n(\epsilon)]\log[1-\alpha n(\epsilon)]\big\}d\epsilon \nonumber
  \\
  &=& -\frac{k_{\rm B}^2 T\zeta_n}{h} [2Li_2(-y_{i,0}) + \log{(1+y_{i,0})}\log{y_{i,0}}] \label{entropia_flux} ,
\end{eqnarray}
and represents the flux of the number of configurations of particle populations, $\{n(\epsilon)\}$, from one reservoir to the other. But Eq. (\ref{entropia_flux}) is identical in form with Eq. (\ref{entropia}) and therefore it is independent of $\alpha$ at any temperature.

To clarify the microscopic reason for which the 1D entropy and heat fluxes are independent of statistics, we use Eqs. (\ref{IUpoly}) and the relation $Li_2(x)+Li_2[-x/(1-x)]=-\frac{1}{2}\log^2(1-x)$ \cite{Lewin:book} to write
\begin{eqnarray}
  \dot U_{n,1}(\mu_i,T_i) &=& \frac{\alpha hI_{n,1}^2}{2\zeta_n} + \frac{\zeta_n(k_BT_i)^2}{h}Li_2\left(\frac{y_{0,i}}{y_{0,i}+1}\right) \nonumber \\
  &\equiv& \dot U_{0,n,1}(I_{n,1}) + \dot U_{B,n,1}(I_{n,1},T_i)  \label{def_dotUB}
\end{eqnarray}
where $\dot U_{0,n,1}$ is the energy flux at zero temperature and $\dot U_{B,n,1}$ is the excitation energy flux--in a Bose gas, $\dot U_{0,n,1}\equiv0$ and $\dot U_{n,1}\equiv\dot U_{B,n,1}$, hence the notation. As one can see directly from Eq. (\ref{def_dotUB}), $\dot U_{B,n,1}$ is independent of $\alpha$ at any temperature and therefore at zero net current, $I_{n,1}(\mu_1,T_1)-I_{n,1}(\mu_2,T_2)=0$, the heat flux is equal to the difference between the excitation energy fluxes,
\begin{equation}
  \dot U_n = \dot U_{B,n,1}(I_{n,1},T_2)-\dot U_{B,n,1}(I_{n,1},T_1), \label{dotUN_B}
\end{equation}
which is independent of $\alpha$ at any $T$.

The statistics independence of $\dot U_{B,n,1}(I,T)$ at any $T$ may be interpreted microscopically also starting from the analogy with the equilibrium thermodynamics of systems of constant DOS. In Ref. \cite{JPA35.7255.2002.Anghel} it was proven that for systems of particles of different statistics, but the same, constant DOS and particle number, there is a one-to-one mapping between configurations of particle populations, $\{n(\epsilon)\}$, which have the same excitation energy. This implies that the canonical partition functions of such systems are independent of $\alpha$ and therefore all their canonical thermodynamics is independent of statistics, including the entropy and the heat capacity.

\begin{figure}[t]

  \includegraphics[width=6cm]{B_F_flux.eps}

\caption{The microscopic analysis of the statistics independence of the heat conductivity: there is a one-to-one correspondence between micro-configurations of particles of different statistics which have the same excitation energy, $\dot U_{B,n,1}$, and therefore carry the same heat-fluxes.}
\label{B_F_flux}
\end{figure}

The same argument can be transcribed for energy fluxes in 1D channels. If we have two gases, one of parameter $\alpha$ and another of parameter $\alpha'$, both gases carrying the same particle flux, $I_{n,1}$, through a 1D channel, then one can establish a one-to-one correspondence between configurations of particle populations in the two gases, with the same $\dot U_{B,n,1}$. Two such configurations, one of bosons and one of fermions, are shown in Fig. \ref{B_F_flux}. This implies that both, the excitation energy flux and the entropy flux (which is determined by the flux of the number of configurations), are independent of statistics.

In conclusion I showed that the particle, energy, entropy and heat fluxes through a 1D channel are analogue to the particle number, internal energy, entropy and the heat capacity of a gas of constant density of states. Using this analogy, I wrote analytical expressions for all the fluxes and their derivatives with respect to the chemical potential and temperature, I calculated their asymptotic expressions in the limit $T\to0$, and I showed that the heat and entropy fluxes are independent of the statistics of the particles involved in the transport at any temperature, not only when $T\to0$, as it was known before. Using a construction I introduced in Ref. \cite{JPA35.7255.2002.Anghel}, I showed what is the microscopic reason for the independence of statistics of the constituent particles for heat and entropy fluxes in 1D channels.

The financial support from the Romanian National Authority for Scientific Research grant PN 09370102, and the Romanian, IFIN-HH–JINR collaboration grants 4027-3-10/11 and N4006 is gratefully acknowledged.


\section{Introduction}

\vspace*{-.15cm}

The concept of parsimony is central in many scientific domains. In the context of statistics, signal processing or machine learning, it may take several forms. Classically, in a variable or feature selection problem, a sparse solution with many zeros is sought so that the model is either more interpretable, cheaper to use, or simply matches available prior knowledge (see, e.g.,~\cite{Zhaoyu,negahban2009unified,bach2010structured} and references therein).
In this paper, we instead consider sparsity-inducing regularization terms that will lead to  solutions with \emph{many equal values}. A classical example is the total variation in one or two dimensions, which leads to piecewise constant solutions~\cite{tibshirani2005sparsity,chambolle2009total} and can be applied to various image labelling problems~\cite{boykov2001fast,chambolle2009total}, or change point detection tasks~\cite{harchaoui2008catching,bleakley,kolar2009sparsistent}. Another example is the ``Oscar'' penalty which induces automatic grouping of the features~\cite{oscar}. In this paper, we follow the approach of~\cite{bach2010structured}, who designed sparsity-inducing norms based on \emph{non-decreasing} submodular functions, as a convex approximation to imposing a specific prior on the \emph{supports} of the predictors. Here, we show that a similar parallel holds for some other class of submodular functions, namely non-negative set-functions which are equal to zero for the full and empty set. Our main instance of such functions are \emph{symmetric} submodular functions.

We make the following contributions:
\begin{itemize}
\item[$-$] We provide in \mysec{properties} explicit links between priors on level sets and certain submodular functions: we show  that the Lov\'asz  extensions (see, e.g.,~\cite{submodular_tutorial} and a short review in \mysec{submodular}) associated to  these  submodular functions are the convex envelopes (i.e., tightest convex lower bounds) of  specific functions that depend on all level sets of the underlying vector.

\item[$-$] In \mysec{examples}, we reinterpret existing norms such as the total variation and design new norms, based on noisy cuts or order statistics. We propose applications to clustering and outlier detection, as well as to change point detection in the presence of outliers.

\item[$-$] We provide unified algorithms in \mysec{algorithms}, such as proximal operators, which are based on a sequence of submodular function minimizations (SFMs), when such SFMs are efficient, or by adapting the generic slower approach of~\cite{bach2010structured} otherwise.

\item[$-$] We derive unified theoretical guarantees for level set recovery in \mysec{theory}, showing that even in the absence of correlation between predictors, level set recovery is not always guaranteed, a situation which is to be contrasted with traditional support recovery situations~\cite{Zhaoyu,bach2010structured}.
 \end{itemize}

\vspace*{-.2cm}

\paragraph{Notation.}
For $w \in \mathbb{R}^p$ and $q \in [1,\infty]$, we  denote by $\| w\|_q$ the $\ell_q$-norm
of $w$.  Given a subset $A $ of  $V = \{1,\dots,p\}$, $1_A \in \{0,1\}^p$ is the indicator vector of the subset $A$.
Moreover, given a vector $w$ and a matrix~$Q$, $w_A$ and $Q_{AA}$ denote the corresponding subvector and submatrix of $w$ and $Q$. Finally, for $w \in \mathbb{R}^p$ and $A \subset V$, $w(A)=\sum_{k \in A} w_k = w^\top 1_A $ (this defines a modular set-function). In this paper, for a certain vector $w \in \mathbb{R}^p$, we call \emph{level sets} the sets of indices which are larger (or smaller) or equal to a certain constant $\alpha$, which we denote $\{ w \geqslant \alpha\}$
(or $\{ w \leqslant \alpha\}$), while we call \emph{constant sets} the sets of indices which are equal to a constant $\alpha$, which we denote $\{ w = \alpha\}$.

\section{Review of Submodular Analysis}
\label{sec:submodular}

\vspace*{-.1cm}

In this section, we review relevant results from submodular analysis. For more details, see, e.g.,~\cite{fujishige2005submodular}, and, for a review with proofs derived from classical convex analysis, see, e.g., \cite{submodular_tutorial}.

\textbf{Definition.} \hspace*{.05cm}
Throughout this paper, we consider a \emph{submodular} function $F$ defined on the power set $2^V$ of $V = \{1,\dots,p\}$, i.e., such that $
 \forall A,B \subset V, \   F(A) + F(B) \geqslant F(A \cup B) + F(A \cap B)$.
 Unless otherwise stated, we consider functions which are non-negative (i.e., such that $F(A) \geqslant 0$ for all $A \subset V$), and that satisfy $F(\varnothing) = F(V)=0$. Usual examples are symmetric submodular functions, i.e., such that $\forall A \subset V, F(V \backslash A) = F(A)$, which are known to always have non-negative values. We give several examples in \mysec{examples}; for illustrating the   concepts introduced in this section  and \mysec{properties}, we will consider the cut in an undirected chain graph, i.e., $F(A) = \sum_{j=1}^{p-1}|(1_A)_{j} - (1_A)_{j+1}|$.

\textbf{Lov\'asz  extension.} \hspace*{.05cm}
 Given any set-function $F$ such that $F(V)=F(\varnothing)=0$, one can define its \emph{Lov\'asz  extension} $f: \mathbb{R}^p \to \mathbb{R}$, as $
 f(w) = \int_\mathbb{R} F( \{w \geqslant \alpha \}) d\alpha$ (see, e.g., \cite{submodular_tutorial} for this particular formulation).
The Lov\'asz  extension is convex if and only if $F$ is submodular. Moreover, $f$ is piecewise-linear and for all $A \subset V$, $f(1_A) = F(A)$, that is, it is indeed an extension from $2^V$ (which can be identified to $\{0,1\}^p$ through indicator vectors) to $\mathbb{R}^p$. Finally, it is always positively homogeneous. For the chain graph, we obtain the usual total variation $f(w) =\sum_{j=1}^{p-1} |w_j-w_{j+1}|$.

\textbf{Base polyhedron.} \hspace*{.05cm}
We denote by $B(F)= \{ s \in \mathbb{R}^p, \ \forall A \subset V, \  s(A)\leqslant F(A), \ s(V) = F(V) \}$ the \emph{base polyhedron}~\cite{fujishige2005submodular},
where we use the notation $s(A) = \sum_{k \in A} s_k$.
One important result in submodular analysis is that if $F$ is a submodular function, then we have a representation of $f$ as a maximum of linear functions~\cite{fujishige2005submodular,submodular_tutorial}, i.e.,  for all $w \in \mathbb{R}^p$, $
f(w) = \max_{ s \in B(F) } \  w^\top s$.
Moreover, instead of solving a linear program with $2^p$ contraints, a solution $s$ may   be obtained by the following ``greedy algorithm'':
order the components of $w$ in decreasing order $w_{j_1} \geqslant \dots \geqslant w_{j_p}$, and then take for all $k \in   \{1,\dots,p\}$,
$s_{j_k} = F( \{ j_1,\dots,j_k\} ) - F( \{ j_1,\dots,j_{k-1}\} ) .$

\textbf{Tight and inseparable sets.} \hspace*{.05cm} The polyhedra~$\mathcal{U} = \{ w \in \mathbb{R}^p, f(w) \leqslant 1 \}$ and $B(F)$ are polar to each other~(see, e.g.,~\cite{rockafellar97} for definitions and properties of polar sets). Therefore, the facial structure of $ \mathcal{U}$ may be obtained from the one of $B(F)$. Given $s \in B(F)$, a set $A \subset V$ is said \emph{tight} if $s(A)=F(A)$. It is known that the set of tight sets is a distributive lattice, i.e., if $A$ and $B$ are tight, then so are $A \cup B$ and $A \cap B$~\cite{fujishige2005submodular,submodular_tutorial}.
The faces of $B(F)$ are thus intersections of hyperplanes $\{ s(A) = F(A) \}$ for $A$  belonging to certain distributive lattices (see Prop.~\ref{prop:faces}).
A set $A$ is said \emph{separable} if there exists a non-trivial partition of $A = B \cup C$ such that $F(A) = F(B)+F(C)$. A set is said inseparable if it is not separable. For the cut in an undirected graph, inseparable sets are exactly connected sets.

\section{Properties of the Lov\'asz  Extension}
\label{sec:properties}

\vspace*{-.1cm}

 In this section, we derive properties of the Lov\'asz  extension for submodular functions, which go beyond convexity and homogeneity. Throughout this section, we assume that $F$ is  a non-negative submodular  set-function that is equal to zero at $\varnothing$ and $V$. This immediately implies that  $f$   is invariant by addition of any constant vector (that is, $f(w+ \alpha 1_V) = f(w)$ for all $w \in \mathbb{R}^p$ and $\alpha \in \mathbb{R}$), and that $f(1_V) = F(V) = 0$. Thus, contrary to the non-decreasing case~\cite{bach2010structured}, our regularizers are not norms. However, they are norms on the hyperplane $\{w^\top 1_V = 0\}$ as soon as for $A \neq \varnothing$ and $A \neq V$, $F(A)>0$ (which we assume for the rest of this paper).

 We now show that the Lov\'asz  extension is the convex envelope of a certain combinatorial function which does depend on all levets sets $\{ w \geqslant \alpha\}$ of $w \in \mathbb{R}^p$  (see proof in supplementary material):
\begin{proposition}[Convex envelope]
\label{prop:envelope}

The Lov\'asz  extension $f(w)$ is the convex envelope of the function
$w \mapsto \max_{ \alpha \in \mathbb{R}}  F( \{ w \geqslant \alpha \} )$ on the set $[0,1]^p + \mathbb{R} 1_V = \{ w \in \mathbb{R}^p , \ \max_{k \in V} w_k - \min_{k \in V} w_k \leqslant 1 \}$.
\end{proposition}

Note the difference with the result of~\cite{bach2010structured}: we consider here a different set on which we compute the convex envelope ($[0,1]^p + \mathbb{R} 1_V$ instead of $[-1,1]^p$), and not a function of the support of $w$, but of \emph{all} its level sets.\footnote{Note that the support $\{ w = 0 \}$ is a constant set which is the intersection of two level sets.} Moreover, the Lov\'asz  extension is a convex relaxation of a function of \emph{level sets} (of the form $\{w \geqslant \alpha\}$) and not of \emph{constant sets} (of the form $\{w = \alpha\}$). It
 would have been perhaps more intuitive to consider for example $\int_\mathbb{R} F( \{ w = \alpha \} ) d\alpha$, since it does not depend on the ordering of the values that $w$ may take; however, the latter function does not lead to a convex function amenable to polynomial-time algorithms.
 This definition through level sets will generate some potentially undesired behavior (such as the well-known staircase effect for the one-dimensional total variation), as we show in \mysec{theory}.

The next proposition describes the set of extreme points of  the ``unit ball'' $\mathcal{U} = \{ w, \ f(w) \leqslant 1\}$, giving a first illustration of sparsity-inducing effects (see example in \myfig{balls}).
\begin{proposition}[Extreme points]
\label{prop:extreme}
The extreme points of the set  $\mathcal{U} \cap \{ w^\top 1_V =0 \}$ are the projections of the vectors $1_A / F(A)$ on the plane $\{  w^\top 1_V = 0\}$, for $A$ such that $A$ is inseparable for $F$ and $V \backslash A$ is inseparable for $B \mapsto F(A \cup B) - F(A)$.
\end{proposition}

\begin{figure}
\begin{center}

 \vspace*{-.75cm}

  \hspace*{-.5cm} \includegraphics[scale=.42]{ball_1_symm_withcomments_nips.eps}  \hspace*{-.5cm}
\includegraphics[scale=.42]{ball_2_symm_nips.eps}   \hspace*{-.5cm}
\end{center}

 \vspace*{-.6cm}

\caption{Top: Polyhedral level set of $f$ (projected on the set $ w^\top 1_V=0$), for 2 different submodular symmetric functions of three variables, with different inseparable sets leading to different sets of extreme points; changing values of $F$ may make some of the extreme points disappear. The various extreme points cut the space into polygons where the ordering of the component is fixed. Left: $F(A) = 1_{|A| \in \{1,2\}}$ (all possible extreme points); note that the polygon need not be symmetric in general. Right: one-dimensional total variation on three nodes, i.e., $F(A) = |1_{ 1 \in A } - 1_{ 2 \in A }| + |1_{ 2 \in A } - 1_{ 3 \in A }|$, leading to $f(w) = |w_1-w_2| + |w_2-w_3|$, for which the extreme points corresponding to the separable set $\{1,3\}$ and its complement disappear.
}
\label{fig:balls}

  \vspace*{-.25cm}

\end{figure}

\textbf{Partially ordered sets and distributive lattices.} \hspace*{.05cm}
A subset $\mathcal{D}$ of $2^V$ is a (distributive) lattice if it is invariant by intersection and union. We assume in this paper that all lattices contain the empty set $\varnothing$ and the full set $V$, and we endow the lattice with the inclusion order.
Such lattices may be represented as a \emph{partially ordered set (poset)} $\Pi(\mathcal{D}) = \{ A_1,\dots,A_m\}$ (with order relationship $\succcurlyeq$), where the sets $A_j$, $j=1,\dots,m$, form a \emph{partition} of $V$ (we always assume a topological ordering of the sets, i.e., $A_i \succcurlyeq A_j \Rightarrow i \geqslant  j$). As illustrated in \myfig{posets}, we go from $\mathcal{D}$ to $\Pi(\mathcal{D})$, by considering all maximal chains in $\mathcal{D}$ and the differences between consecutive sets.
We go from $\Pi(\mathcal{D})$ to $\mathcal{D}$, by constructing all \emph{ideals} of $\Pi(\mathcal{D})$, i.e., sets $J$ such that if an element of $\Pi(\mathcal{D})$ is lower than an element of $J$, then it has to be in $J$~(see \cite{fujishige2005submodular} for more details, and an example in \myfig{posets}).
Distributive lattices and posets are thus in one-to-one correspondence. Throughout this section, we go back and forth between these two representations. The distributive lattice will correspond to all authorized level sets $\{ w \geqslant \alpha\}$ in a single face of $\mathcal{U}$, while the elements of the poset are the constant sets (over which $w$ is constant), with the order between the subsets giving \emph{partial} constraints between the values of the corresponding constants.

\begin{figure}
\begin{center}

 \vspace*{-.25cm}

\includegraphics[scale=.6]{posets_nips_falt.eps}

\vspace*{-.5cm}

\end{center}
\caption{Left: distributive lattice with 7 elements in $2^{\{1,2,3,4,5,6\}}$, represented with the Hasse diagram corresponding to the inclusion order (for a partial order, a Hasse diagram connects $A$ to $B$ if $A$ is smaller than $B$ and there is no $C$ such that $A$ is smaller than $C$ and $C$ is smaller than $B$). Right: corresponding poset, with 4 elements that form a partition of $\{1,2,3,4,5,6\}$, represented with the Hasse diagram corresponding to the order $\succcurlyeq$ (a node points to its immediate smaller node according to $\succcurlyeq$). Note that this corresponds to an ``allowed''  lattice  (see Prop.~\ref{prop:faces}) for the one-dimensional total variation.
}
\label{fig:posets}

 \vspace*{-.5cm}

\end{figure}

\textbf{Faces of $\mathcal{U}$.}  \hspace*{.05cm}
The faces of $\mathcal{U}$ are characterized by lattices $\mathcal{D}$, with their corresponding posets $\Pi(\mathcal{D}) = \{ A_1,\dots,A_m\}$. We denote by $\mathcal{U}^\circ_\mathcal{D}$ (and by $\mathcal{U}_\mathcal{D}$ its closure) the set of $w \in \mathbb{R}^p$ such that (a) $w$ is piecewise constant with respect to $\Pi(\mathcal{D})$, with value $v_i$ on $A_i$, and (b) for all pairs $(i,j)$, $A_i \succcurlyeq  A_j \Rightarrow v_i > v_j$. For certain lattices $\mathcal{D}$, these will be exactly the relative interiors of all faces of~$\mathcal{U}$:
\begin{proposition}[Faces of $\mathcal{U}$]
\label{prop:faces}
The (non-empty) relative interiors of all faces of $\mathcal{U}$ are exactly of the form $\mathcal{U}^\circ_\mathcal{D}$, where $\mathcal{D}$ is a lattice such that:
\\[.1cm]
  (i) the restriction of $F$  to $\mathcal{D}$ is modular, i.e., for all $A,B \in \mathcal{D}$,
$F(A) + F(B) = F(A \cup B) + F( A \cap B)$,
\\[.1cm]
(ii) for all  $j \in \{1,\dots,m\}$, the set $A_j$ is inseparable for the function $C_j \mapsto F(B_{j-1} \cup C_j) - F(B_{j-1})$, where $B_{j-1}$ is the union of all ancestors of $A_j$ in $\Pi(\mathcal{D})$,
\\[.1cm]
(iii) among all lattices corresponding to the same \emph{unordered} partition, $\mathcal{D}$ is a maximal element of the set of lattices satisfying (i) and (ii).
\end{proposition}
Among the three conditions, the second one is the easiest to interpret, as it reduces to having constant sets which are inseparable for certain submodular functions, and for cuts in an undirected graph, these will exactly be connected sets.

Since we are able to characterize \emph{all} faces of $\mathcal{U}$ (of all dimensions) with non-empty relative interior, we have a partition of the space and any $w \in \mathbb{R}^p$ which is not proportional to $1_V$, will be, up to the strictly positive constant $f(w)$, in exactly one of these relative interiors of faces; we refer to this lattice as the \emph{lattice associated to} $w$. Note that from the face $w$ belongs to, we have strong constraints on the constant sets, but we may not be able to determine all level sets of $w$, because only partial constraints are given by the order on $\Pi(\mathcal{D})$. For example, in \myfig{posets}, $w_2$ may be larger or smaller than $w_5 = w_6$ (and even potentially equal, but with zero probability, see \mysec{theory}).

\section{Examples of Submodular Functions}
\label{sec:examples}

\vspace*{-.1cm}

In this section, we provide examples of submodular functions and of their Lov\'asz  extensions. Some are well-known (such as cut functions and total variations), some are new in the context of supervised learning (regular functions), while some have interesting effects in terms of clustering or outlier detection (cardinality-based functions).

\textbf{Symmetrization.} \hspace*{.05cm}
From any submodular function $G$, one may define
$F(A) = G(A) + G( V \backslash A) - G(\varnothing) - G(V)$, which is symmetric. Potentially interesting examples which are beyond the scope of this paper are mutual information, or functions of eigenvalues of submatrices~\cite{bach2010structured}.

\textbf{Cut functions.} \hspace*{.05cm}
\label{sec:cuts}
 Given a set of \emph{nonnegative} weights $d:V \times V \to \mathbb{R}_+$, define  the cut
$F(A) = \sum_{k \in A, j \in V \backslash A} d(k,j)$.  The Lov\'asz  extension is equal to
$f(w) = \sum_{k,j \in V} d(k,j) ( w_k - w_j )_+$ (which shows submodularity because $f$ is convex), and is often referred to as the total variation. If  the weight function $d$ is symmetric, then the submodular function is also symmetric. In this case, it can be shown that inseparable sets for  functions $A \mapsto F(A \cup B) - F(B)$ are exactly \emph{connected} sets. Hence, constant sets are connected sets, which is the usual justification behind the total variation. Note however that some configurations of connected sets are not allowed due to the other conditions in Prop.~\ref{prop:faces} (see examples in \mysec{theory}).
 In \myfig{speed} (right plot), we give an example of the usual chain graph, leading to the one-dimensional total variation~\cite{tibshirani2005sparsity,chambolle2009total}.
Note that these functions can be extended to cuts in hypergraphs, which may have interesting applications in computer vision~\cite{boykov2001fast}. Moreover, directed cuts may be interesting to favor increasing or decreasing jumps along the edges of the graph.

\begin{figure}
\begin{center}

 \vspace*{-.25cm}

\hspace*{-1.25cm}
\parbox[b]{10.5cm}{
\includegraphics[scale=.26]{icml_noisycut_original.eps} \hspace*{-.2cm}
\includegraphics[scale=.26]{icml_noisycut_TV.eps} \hspace*{-.2cm}
\includegraphics[scale=.26]{icml_noisycut_TVnoisy.eps}

\vspace*{.25cm}}
\includegraphics[scale=.38]{plot_noisy_cuts.eps}
\hspace*{-.95cm}

\end{center}

\vspace*{-.6cm}

\caption{\textbf{Three left plots}: Estimation of noisy piecewise constant 1D signal with outliers (indices 5 and 15 in the chain of 20 nodes). Left: original signal. Middle: best estimation with total variation (level sets are not correctly estimated). Right: best estimation with the  \emph{robust} total variation based on noisy cut functions (level sets are correctly estimated, with less bias and with detection of outliers).  \textbf{Right plot}: clustering estimation error vs. noise level, in a sequence of 100 variables, with a single jump, where noise of variance one is added, with $5\%$ of outliers (averaged over 20 replications).}
\label{fig:noisycuts}

 \vspace*{-.25cm}

\end{figure}

\textbf{Regular functions and robust total variation.} \hspace*{.05cm}
\label{sec:regular}
By partial minimization, we obtain so-called \emph{regular functions}~\cite{boykov2001fast, chambolle2009total}. One application is ``noisy cut functions'':
  for a given  weight function $d: W \times W \to \mathbb{R}_+$,  where each node in $W$ is uniquely associated in a node in $V$, we consider the submodular function obtained as the minimum cut adapted to $A$ in the augmented graph (see right plot of \myfig{speed}):
$
F(A) =  \min_{B \subset W} \  \sum_{k \in B, \ j \in W \backslash B} d(k,j) + \lambda | A \Delta B|$.
 This allows for robust versions of cuts, where some gaps may be tolerated. See examples in \myfig{noisycuts}, illustrating the behavior of the type of graph displayed in the bottom-right plot of \myfig{speed}, where the performance of the robust total variation is significantly more stable in presence of outliers.

\textbf{Cardinality-based functions.} \hspace*{.05cm}
\label{sec:card}
For $F(A) = h(|A|)$ where $h$ is such that $h(0)=h(p)=0$ and $h$ concave, we obtain a submodular function, and a Lov\'asz  extension that depends on the order statistics of $w$, i.e., if $w_{j_1} \geqslant \dots \geqslant w_{j_p}$, then $f(w) = \sum_{k=1}^{p-1} h(k) ( w_{j_k} - w_{j_{k+1}})$. While these examples do not provide significantly different behaviors for the non-decreasing submodular functions explored by~\cite{bach2010structured} (i.e., in terms of \emph{support}), they lead to interesting behaviors here in terms of \emph{level sets}, i.e., they will make the components $w$ cluster together in specific ways.  Indeed, as shown in \mysec{theory}, allowed constant sets $A$ are such that $A$ is inseparable for the function $C \mapsto h(|B \cup C|) - h(|B|)$ (where $B \subset V$ is the set of components with higher values than the ones in $A$), which imposes that  the concave function $h$ is not linear on $[|B|,|B|\!+\!|A|]$. We consider the following examples:

\vspace*{-.1cm}

\begin{enumerate}
\setlength{\leftmargin}{0pt}
\item $F(A) = |A| \cdot | V \backslash A| $, leading to
$f(w) = \sum_{i,j=1}^p |w_i - w_j|$. This function can thus be also seen as the cut in the fully connected graph. All patterns of level sets are allowed as the function~$h$ is strongly concave (see left plot of \myfig{card}). This function has been extended in~\cite{toby} by considering situations where each $w_j$ is a vector, instead of a scalar, and replacing the absolute value $| w_i - w_j|$ by any norm $\| w_i - w_j\|$, leading to convex formulations for clustering.

\vspace*{-.05cm}

\item $F(A) =  1$  if $A \neq \varnothing$ and $A \neq V$, and $0$ otherwise, leading to
$f(w) = \max_{i,j} | w_i - w_j|$. Two large level sets at the top and bottom, all the rest of the variables are in-between and separated (\myfig{card}, second plot from the left).

\vspace*{-.05cm}

\item $F(A) =  \max\{ |A|,  | V \backslash A| \} $. This function is piecewise affine, with only one kink, thus only one level set of cardinalty greater than one (in the middle) is possible, which is observed in \myfig{card} (third plot from the left). This may have applications to multivariate outlier detection by considering extensions similar to~\cite{toby}.

\end{enumerate}

\vspace*{-.195cm}

\section{Optimization Algorithms}
\label{sec:algo}
\label{sec:algorithms}
\label{sec:opt}

\vspace*{-.15cm}

In this section, we present optimization methods for minimizing convex objective functions regularized by the Lov\'asz  extension of a submodular function. These lead to convex optimization problems, which we tackle using proximal methods~(see, e.g., \cite{beck2009fast}). We first start by mentioning that subgradients may easily be derived (but subgradient descent is here rather inefficient as shown in \myfig{speed}).  Moreover, note that with the square loss, the regularization paths are piecewise affine, as a direct consequence of regularizing by a polyhedral function.

\textbf{Subgradient.} \hspace*{.05cm}
From $f(w) = \max_{ s \in B(F)} s^\top w$ and the greedy algorithm\footnote{The greedy algorithm to find extreme points of the base polyhedron should not be confused with the greedy algorithm (e.g., forward selection) that is common in supervised learning/statistics.} presented in \mysec{submodular}, one can easily get in \emph{polynomial time} one subgradient as one of the maximizers $s$. This allows to use subgradient descent, with slow convergence compared to proximal methods (see \myfig{speed}).

\begin{figure}
\begin{center}

 \vspace*{-.25cm}

\hspace*{-2.2cm}
\includegraphics[scale=.28]{icml_card_quad.eps}
\includegraphics[scale=.28]{icml_card_max.eps}
\includegraphics[scale=.28]{icml_card_linear.eps}
\includegraphics[scale=.28]{icml_cut.eps}
\hspace*{-1.5cm}

\end{center}

\vspace*{-.5cm}

\caption{\textbf{Left:} Piecewise linear regularization paths of  proximal problems (\eq{prox}) for different functions of cardinality. From left to right: quadratic function (all level sets allowed),  second example in \mysec{card}  (two large level sets at the top and bottom),   piecewise linear with two pieces (a single large level set in the middle). \textbf{Right:} Same plot for the one-dimensional total variation.  Note that in both cases the regularization paths for orthogonal designs are \emph{agglomerative} (see \mysec{opt}), while for general designs, they would still be piecewise affine but not agglomerative. }
\label{fig:card}

\end{figure}

\textbf{Proximal problems through sequences of submodular function minimizations (SFMs).} \hspace*{.05cm}
Given regularized problems of the form $\min_{w \in \mathbb{R}^p} L(w) + \lambda f(w)$, where $L$ is differentiable with Lipschitz-continuous gradient, \emph{proximal methods} have been shown to be particularly efficient first-order methods~(see, e.g.,~\cite{beck2009fast}). In this paper, we use the method ``ISTA'' and its accelerated variant ``FISTA''~\cite{beck2009fast}.
To apply these methods, it suffices to be able to
solve efficiently:
\begin{equation}
\label{eq:prox}
\min_{ w \in \mathbb{R}^p} \textstyle \frac{1}{2} \| w - z \|_2^2 + \lambda f(w),
\end{equation}
 which we refer to as the \emph{proximal problem}. It is known that solving the proximal problem is related to  submodular function minimization (SFM).
More precisely, the minimum of $A \mapsto \lambda F(A) - z(A)$ may be obtained by selecting negative components of the solution of a single proximal problem~\cite{fujishige2005submodular,submodular_tutorial}. Alternatively, the solution of the proximal problem may be obtained by a sequence of at most~$p$ submodular function minimizations of the form $A \mapsto \lambda F(A) - z(A)$, by a decomposition algorithm adapted from~\cite{groenevelt1991two}, and described in~\cite{submodular_tutorial}.

Thus, computing the proximal operator has polynomial complexity since SFM has polynomial complexity. However, it may be  too slow for practical purposes, as the best \emph{generic} algorithm has complexity $O(p^6)$~\cite{orlin2009faster}\footnote{Note that even in the case of symmetric submodular functions, where more efficient algorithms  in $O(p^3)$ for submodular function minimization (SFM) exist~\cite{queyranne1998minimizing}, the minimization of functions of the form $\lambda F(A) - z(A)$ is provably as hard as general SFM~\cite{queyranne1998minimizing}.}. Nevertheless, this strategy is efficient
 for families of submodular functions for which dedicated fast algorithms exist:
\begin{itemize}
\item[--] \textbf{Cuts}: Minimizing the cut or the partially minimized cut, plus a modular function, may be done with a min-cut/max-flow algorithm~(see, e.g., \cite{boykov2001fast,chambolle2009total}).
 For proximal methods,  we need in fact to solve an instance of a \emph{parametric max-flow} problem, which may be done using other efficient dedicated algorithms~\cite{gallo1989fast,chambolle2009total} than the decomposition algorithm derived from~\cite{groenevelt1991two}.
\item[--] \textbf{Functions of cardinality}: minimizing functions of the form $A \mapsto \lambda F(A) - z(A)$ can be done in closed form by sorting the elements of $z$.
\end{itemize}

\textbf{Proximal problems through minimum-norm-point algorithm.} \hspace*{.05cm}
In the \emph{generic} case (i.e., beyond cuts and cardinality-based functions), we can follow~\cite{bach2010structured}: since $f(w)$ is expressed as a minimum of linear functions, the problem reduces to the projection on the polytope $B(F)$, for which we happen to be able to easily  maximize linear functions (using the greedy algorithm described in \mysec{submodular}). This  can be tackled efficiently by the minimum-norm-point algorithm~\cite{fujishige2005submodular}, which iterates between orthogonal projections on affine subspaces and the greedy algorithm for the submodular function\footnote{Interestingly, when used for submodular function minimization (SFM), the minimum-norm-point algorithm has no complexity bound but is empirically faster than algorithms with such bounds~\cite{fujishige2005submodular}.}. We compare all optimization methods on synthetic examples in \myfig{speed}.

\textbf{Proximal path as agglomerative clustering.} \hspace*{.05cm}
When $\lambda$ varies from zero to $+\infty$, then the unique optimal solution of \eq{prox} goes from $z$ to a constant. We now provide conditions under which the regularization path of the proximal problem may be obtained by agglomerative clustering (see examples in \myfig{card}):
\begin{proposition}[Agglomerative clustering]
\label{prop:agglo}
Assume that for all sets $A,B$ such that $B \cap A = \varnothing$ and  $A$ is inseparable for $D \mapsto F(B \cup D) - F(B)$, we have:

\vspace*{-.35cm}

\begin{equation}
\label{eq:agglo}
\textstyle \forall C \subset A, \ \frac{|C|}{|A|} [ F( B \cup A) - F(B) ]
\leqslant   F( B \cup C) - F(B) .
\end{equation}

\vspace*{-.2cm}

Then the   regularization path for \eq{prox} is \emph{agglomerative}, that is, if two variables are in the same constant for a certain $\mu \in \mathbb{R}_+$, so are they for all larger $\lambda \geqslant \mu$.
\end{proposition}
As shown in the supplementary material, the assumptions required for by Prop.~\ref{prop:agglo} are satisfied by (a) all submodular set-functions that only depend on the cardinality, and (b) by the one-dimensional total variation---we thus recover and extend known results from~\cite{harchaoui2008catching,hoefling910path,toby}.

\textbf{Adding an $\ell_1$-norm.} \hspace*{.05cm}
Following~\cite{tibshirani2005sparsity}, we may add the $\ell_1$-norm $\| w\|_1$ for additional sparsity of $w$ (on top of shaping its level sets). The following proposition extends the result for the one-dimensional total variation~\cite{tibshirani2005sparsity,mairal2010online} to all submodular functions and their Lov\'asz  extensions:
\begin{proposition}[Proximal problem for $\ell_1$-penalized problems]
\label{prop:proxL1}
The unique minimizer of $\frac{1}{2} \| w- z \|_2^2 + f(w) + \lambda \| w\|_1$  may be obtained by soft-thresholding
the minimizers of $\frac{1}{2} \| w- z  \|_2^2 + f(w)$. That is, the proximal operator for $f + \lambda \| \cdot \|_1$ is equal to the composition of the proximal operator for $f$ and the one for $\lambda \| \cdot \|_1$.
\end{proposition}

\begin{figure}

\vspace*{-.45cm}

\begin{center}
\hspace*{1cm}
\includegraphics[scale=.35]{figure_running_speed_decent.eps} \hspace*{1cm}
\parbox[b]{5cm}{\hspace*{.1cm} \includegraphics[scale=.4]{cut_3_nost_long.eps}  \\[.1cm]
\includegraphics[scale=.4]{cut_2_nost_long_VW.eps} \vspace*{.2cm}}
\end{center}

\vspace*{-.5cm}

\caption{\textbf{Left}: Matlab running times of different optimization methods on 20 replications of a least-squares regression problem with $p=1000$ for a cardinality-based submodular function (best seen in color). Proximal methods with the generic algorithm (using the minimum-norm-point algorithm) are faster than subgradient descent (with two schedules for the learning rate, $1/t$ or $1/\sqrt{t}$). Using the dedicated algorithm (which is not available in all situations) is significantly faster. \textbf{Right}: Examples of graphs (top:   chain graph, bottom: hidden chain graph, with sets $W$ and $V$ and examples of a set $A$ in light red, and $B$ in blue, see text for details).}
\label{fig:speed}
\end{figure}

\section{Sparsity-inducing Properties}
\label{sec:theory}

\vspace*{-.2cm}

Going from the penalization of supports to the penalization of level sets introduces some complexity and for simplicity in this section, we only consider the analysis in the context of orthogonal design matrices, which is often referred to as the denoising problem, and in the context of level set estimation already leads to interesting results. That is, we study the global minimum of the proximal problem in \eq{prox} and make some assumption regarding $z$ (typically $z = w^\ast + \mbox{ noise} $), and provide guarantees related to the recovery of the level sets of $w^\ast$. We first start by characterizing the allowed level sets, showing that the partial constraints defined in \mysec{properties} on faces of $\{f(w) \leqslant 1\}$ do not create by chance further groupings of variables (see proof in supplementary material).
\begin{proposition}[Stable constant sets]
\label{prop:patterns}
Assume  $z \in \mathbb{R}^p$  has an absolutely continuous density with respect to
the Lebesgue measure. Then, with probability one,  the unique minimizer $\hat{w}$ of \eq{prox} has constant sets that define a partition corresponding to a lattice $\mathcal{D}$ defined in Prop.~\ref{prop:faces}.
  \end{proposition}
We now show that under certain conditions the recovered constant sets are the correct ones:\\[-.5cm]
\begin{theorem}[Level set recovery]
\label{theo:support}
Assume that $z = w^\ast + \sigma \varepsilon$, where $\varepsilon \in \mathbb{R}^p $ is a standard Gaussian random vector, and $z^\ast$ is consistent with the lattice $\mathcal{D}$ and its associated poset $\Pi(\mathcal{D}) = (A_1,\dots,A_m)$, with values $v^\ast_j$ on $A_j$, for $j \in \{1,\dots,m\}$. Denote $B_j = A_1 \cup \cdots \cup A_j$ for $j \in \{1,\dots,m\}$.
Assume that there exists some constants $\eta_j>0$ and $\nu>0$  such that:
\begin{eqnarray}
\label{eq:eta}
&\textstyle
\hspace*{-.45cm}
 \forall C_j \!\subset\! A_j,
F(B_{j-1} \!\cup\! C_j) \!-\!  F(B_{j-1} ) \!-\! \frac{ |C_j|}{|A_j|}  [ F(B_{j-1}\! \cup \! A_j) \!-\! F(B_{j-1}) ]
\geqslant \eta_j \min \! \big\{
\frac{ |C_j|}{|A_j|}  , 1 \!-\!\frac{ |C_j|}{|A_j|}
\big\}, \ \
\\[-.1cm]
&\label{eq:rho}
\forall i,j \in \{1,\dots,m\} , \  A_i \succcurlyeq A_j  \Rightarrow  v_i^\ast - v_j^\ast \geqslant \nu,
\\[-.1cm]
&
\label{eq:lambda}
\textstyle
\forall j \in \{1,\dots,m\} , \   \lambda  \big| \frac{F(B_{j} ) - F(B_{j-1})}{|A_j|} \big|
\leqslant \nu / 4.\\[-.4cm]
\nonumber
\end{eqnarray}
Then
the unique minimizer $\hat{w}$ of \eq{prox}  is associated to the same lattice  $\mathcal{D}$ than $w^\ast$,
with probability greater than
$
\textstyle 1 - \sum_{j=1}^m \exp\big( -\frac{ \nu^2 |A_j|}{32 \sigma^2} \big) - 2 \sum_{j=1}^m |A_j| \exp\big( - \frac{ \lambda^2 \eta_j^2}{ 2\sigma^2 |A_j|^2 } \big)
$.
\end{theorem}
We now discuss  the three main assumptions of Theorem~\ref{theo:support} as well as the probability estimate:\\[-.6cm]
\begin{itemize}
\item[--] \eq{eta} is the equivalent of the support recovery of the Lasso~\cite{Zhaoyu} or its extensions~\cite{bach2010structured}. The main difference is that for support recovery, this assumption is always met for orthogonal designs, while here it is not always met. Interestingly, the validity of level set recovery  implies the agglomerativity of proximal paths (\eq{agglo} in Prop.~\ref{prop:agglo}).

Note that if  \eq{eta} is satisfied only with $\eta_j \geqslant 0$ (it is then exactly \eq{agglo} in Prop.~\ref{prop:agglo}), then, even with infinitesimal noise, one can show that in some cases, the wrong level sets may be obtained with non vanishing probability, while if $\eta_j$ is strictly negative, one can show that in some cases, we \emph{never} get the correct level sets. \eq{eta} is thus essentially sufficient and necessary.

\item[--] \eq{rho} corresponds to having  distinct values of $w^\ast$  far enough from each other.

\item[--]  \eq{lambda} is a constraint on $\lambda$ which controls the bias  of the estimator: if it is too large, then there may be a merging of two clusters.

\item[--] In the probability estimate, the second term is small if all $\sigma^2 |A_j|^{-1}$ are small enough (i.e., given the noise, there is enough data to correctly estimate the values of the constant sets) and the third term is small if  $\lambda$ is large enough, to avoid that clusters split.
\end{itemize}

\textbf{One-dimensional total variation.} \hspace*{.05cm}
In this situation, we always get $\eta_j=0$, but in some cases, it cannot be improved (i.e., the best possible $\eta_j$ is equal to zero), and as shown in the supplementary material, this occurs as soon as there is a ``staircase'', i.e., a piecewise constant vector, with a sequence of at least two consecutive increases, or two consecutive decreases, showing that in the presence of such staircases, one cannot have consistent support recovery, which is a well-known issue in signal processing (typically, more steps are created).
If there is no staircase effect, we have $\eta_j = 1$ and \eq{lambda} becomes
$\lambda \leqslant \frac{\nu}{8}\min_{j} |A_j| $. If we take $\lambda$ equal to the limiting value in \eq{lambda}, then we obtain a probability less than
$ 1 - 4 p \exp ( - \frac{ \nu^2 \min_{j} |A_j|^2}{ 128 \sigma^2 \max_{j} |A_j|^2 }  ) $.
 Note that we could also derive general results when an additional $\ell_1$-penalty is used, thus extending results from~\cite{rinaldo2009properties}.

 \textbf{Two-dimensional total variation.} \hspace*{.05cm}
 In this situation, even with only two different values for $z^\ast$, then we may have $\eta_j < 0$, leading to additional problems, which has already been noticed in continuous settings (see, e.g.,~\cite{duval:154} and the supplementary material).

 \textbf{Clustering with $F(A) = |A| \cdot | V \backslash A |$.} \hspace*{.05cm}  In this case, we have
 $\eta_j = |A_j|/2$, and \eq{lambda} becomes $\lambda \leqslant \frac{\nu}{4p}$, leading to the probability of correct support estimation greater than
$ 1 - 4 p \exp\big( - \frac{  \nu^2}{ 128 p \sigma^2   } \big)$. This indicates that the noise variance $\sigma^2$ should be small compared to $1/p$, which is not satisfactory and would be corrected with the weighting schemes proposed in~\cite{toby}.

\section{Conclusion}

\vspace*{-.1cm}

We have presented a family of sparsity-inducing norms dedicated to incorporating prior knowledge or structural constraints on the level sets of linear predictors. We have provided a set of common algorithms and theoretical results, as well as simulations on synthetic examples illustrating the behavior of these norms. Several avenues are worth investigating: first, we could follow current practice in sparse methods, e.g., by considering related adapted concave penalties to enhance sparsity-inducing capabilities, or by extending some of the concepts for norms of matrices, with potential applications in matrix factorization~\cite{Srebro2005Maximum} or multi-task learning~\cite{argyriou2008convex}.

\subsection*{Acknowledgements}
 This paper was partially supported by   the Agence Nationale de la Recherche (MGA Project), the European Research Council (SIERRA Project) and Digiteo (BIOVIZ project).

 \newpage